← Back to branch summary

~halega/+junk/sharpdevelop

« back to all changes in this revision

Viewing changes to src/AddIns/Misc/Reports/Irony/Microsoft/BigInteger.cs

  • Committer: sk
  • Date: 2011-09-10 05:17:57 UTC
  • Revision ID: halega@halega.com-20110910051757-qfouz1llya9m6boy
4.1.0.7915 Release Candidate 1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/AddIns/Misc/Reports/Irony/Microsoft/BigInteger.cs
 
1
// Notes from Irony project coordinator (Roman Ivantsov)
 
2
//  1. The code in this file is a copy of the file with the same name from Microsoft.Scripting distribution, 
 
3
//     with a few minor changes made to be able to compile as part of Irony. 
 
4
//     Waiting for MS to provide big integers as part of .NET core distribution - long promised
 
5
//  2. I had to tweak a few static fields to make them readonly, to comply with security requirements 
 
6
//     for SQL Server-imported assemblies. To find the modified fields, search for "RI:" token 
 
7
 
 
8
 
 
9
/* ****************************************************************************
 
10
 *
 
11
 * Copyright (c) Microsoft Corporation. 
 
12
 *
 
13
 * This source code is subject to terms and conditions of the Microsoft Public License. A 
 
14
 * copy of the license can be found in the License.html file at the root of this distribution. If 
 
15
 * you cannot locate the  Microsoft Public License, please send an email to 
 
16
 * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound 
 
17
 * by the terms of the Microsoft Public License.
 
18
 *
 
19
 * You must not remove this notice, or any other, from this software.
 
20
 *
 
21
 *
 
22
 * ***************************************************************************/
 
23
 
 
24
using System;
 
25
using System.Text;
 
26
using System.Collections;
 
27
using System.Collections.Generic;
 
28
using System.Globalization;
 
29
using System.Diagnostics;
 
30
using System.Diagnostics.CodeAnalysis;
 
31
//using Microsoft.Scripting.Utils;
 
32
 
 
33
namespace Microsoft.Scripting.Math {
 
34
  /// <summary>
 
35
  /// arbitrary precision integers
 
36
  /// </summary>
 
37
  [System.ComponentModel.TypeConverter(typeof(BigInteger.TypeConvertor))]
 
38
  public class BigInteger : IFormattable, IComparable, IConvertible {
 
39
 
 
40
    class TypeConvertor : System.ComponentModel.TypeConverter {
 
41
      public override bool CanConvertFrom(System.ComponentModel.ITypeDescriptorContext context, Type sourceType) {
 
42
        if (sourceType == typeof(BigInteger)) {
 
43
          return true;
 
44
        }
 
45
        switch (Type.GetTypeCode(sourceType)) {
 
46
          case TypeCode.Boolean:
 
47
          case TypeCode.DateTime:
 
48
          case TypeCode.DBNull:
 
49
          case TypeCode.Empty:
 
50
          case TypeCode.Object:
 
51
            return false;
 
52
          default:
 
53
            return true;
 
54
        }
 
55
      }
 
56
 
 
57
      public override object ConvertFrom(System.ComponentModel.ITypeDescriptorContext context, CultureInfo culture, object value) {
 
58
        if (value != null) {
 
59
          Type vt = value.GetType();
 
60
          if (vt == typeof(BigInteger)) {
 
61
            return value;
 
62
          }
 
63
          switch (Type.GetTypeCode(vt)) {
 
64
            case TypeCode.Byte:
 
65
              return BigInteger.Create((byte)value);
 
66
            case TypeCode.Char:
 
67
              return BigInteger.Create((char)value);
 
68
            case TypeCode.Int16:
 
69
              return BigInteger.Create((short)value);
 
70
            case TypeCode.Int32:
 
71
              return BigInteger.Create((int)value);
 
72
            case TypeCode.Int64:
 
73
              return BigInteger.Create((long)value);
 
74
            case TypeCode.SByte:
 
75
              return BigInteger.Create((sbyte)value);
 
76
            case TypeCode.UInt16:
 
77
              return BigInteger.Create((ushort)value);
 
78
            case TypeCode.UInt32:
 
79
              return BigInteger.Create((uint)value);
 
80
            case TypeCode.UInt64:
 
81
              return BigInteger.Create((ulong)value);
 
82
            case TypeCode.Decimal:
 
83
              return BigInteger.Create((decimal)value);
 
84
            case TypeCode.Single:
 
85
              return BigInteger.Create((float)value);
 
86
            case TypeCode.Double:
 
87
              return BigInteger.Create((double)value);
 
88
          }
 
89
        }
 
90
        return base.ConvertFrom(context, culture, value);
 
91
      }
 
92
 
 
93
      public override bool CanConvertTo(System.ComponentModel.ITypeDescriptorContext context, Type destinationType) {
 
94
        if (destinationType == typeof(BigInteger)) {
 
95
          return true;
 
96
        }
 
97
        switch (Type.GetTypeCode(destinationType)) {
 
98
          case TypeCode.Boolean:
 
99
          case TypeCode.DateTime:
 
100
          case TypeCode.DBNull:
 
101
          case TypeCode.Empty:
 
102
          case TypeCode.Object:
 
103
            return false;
 
104
          default:
 
105
            return true;
 
106
        }
 
107
      }
 
108
 
 
109
      public override object ConvertTo(System.ComponentModel.ITypeDescriptorContext context, CultureInfo culture, object value, Type destinationType) {
 
110
        if (value != null) {
 
111
          BigInteger bi = (BigInteger)value;
 
112
          Type vt = destinationType;
 
113
          if (vt == typeof(BigInteger)) {
 
114
            return value;
 
115
          }
 
116
          switch (Type.GetTypeCode(vt)) {
 
117
            case TypeCode.Byte:
 
118
              return bi.ToByte(null);
 
119
            case TypeCode.Char:
 
120
              return bi.ToChar(null);
 
121
            case TypeCode.Int16:
 
122
              return bi.ToInt16(null);
 
123
            case TypeCode.Int32:
 
124
              return bi.ToInt32(null);
 
125
            case TypeCode.Int64:
 
126
              return bi.ToInt64(null);
 
127
            case TypeCode.SByte:
 
128
              return bi.ToSByte(null);
 
129
            case TypeCode.UInt16:
 
130
              return bi.ToUInt16(null);
 
131
            case TypeCode.UInt32:
 
132
              return bi.ToUInt32(null);
 
133
            case TypeCode.UInt64:
 
134
              return bi.ToUInt64(null);
 
135
            case TypeCode.Decimal:
 
136
              return bi.ToDecimal(null);
 
137
            case TypeCode.Single:
 
138
              return bi.ToSingle(null);
 
139
            case TypeCode.Double:
 
140
              return bi.ToDouble(null);
 
141
          }
 
142
        }
 
143
        return base.ConvertTo(context, culture, value, destinationType);
 
144
      }
 
145
    }
 
146
 
 
147
    private const int BitsPerDigit = 32;
 
148
    private const ulong Base = 0x100000000;
 
149
 
 
150
    private readonly short sign;
 
151
    private readonly uint[] data;
 
152
 
 
153
    [SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes")]
 
154
    public static readonly BigInteger Zero = new BigInteger(0, new uint[0]);
 
155
    [SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes")]
 
156
    public static readonly BigInteger One = new BigInteger(+1, new uint[] { 1 });
 
157
 
 
158
    [CLSCompliant(false)]
 
159
    public static BigInteger Create(ulong v) {
 
160
      return new BigInteger(+1, (uint)v, (uint)(v >> BitsPerDigit));
 
161
    }
 
162
 
 
163
    [CLSCompliant(false)]
 
164
    public static BigInteger Create(uint v) {
 
165
      if (v == 0) return Zero;
 
166
      else if (v == 1) return One;
 
167
      else return new BigInteger(+1, v);
 
168
    }
 
169
 
 
170
    public static BigInteger Create(long v) {
 
171
      ulong x;
 
172
      int s = +1;
 
173
      if (v < 0) {
 
174
        x = (ulong)-v; s = -1;
 
175
      } else {
 
176
        x = (ulong)v;
 
177
      }
 
178
 
 
179
      //Console.WriteLine("{0}, {1}, {2}, {3}", v, x, (uint)x, (uint)(x >> BitsPerDigit));
 
180
      return new BigInteger(s, (uint)x, (uint)(x >> BitsPerDigit));
 
181
    }
 
182
 
 
183
    public static BigInteger Create(int v) {
 
184
      if (v == 0) return Zero;
 
185
      else if (v == 1) return One;
 
186
      else if (v < 0) return new BigInteger(-1, (uint)-v);
 
187
      else return new BigInteger(+1, (uint)v);
 
188
    }
 
189
 
 
190
    private const Int32 DecimalScaleFactorMask = 0x00FF0000;
 
191
    private const Int32 DecimalSignMask = unchecked((Int32)0x80000000);
 
192
 
 
193
    public static BigInteger Create(decimal v) {
 
194
      // First truncate to get scale to 0 and extract bits
 
195
      int[] bits = Decimal.GetBits(Decimal.Truncate(v));
 
196
 
 
197
      Debug.Assert(bits.Length == 4 && (bits[3] & DecimalScaleFactorMask) == 0);
 
198
 
 
199
      int size = 3;
 
200
      while (size > 0 && bits[size - 1] == 0) size--;
 
201
 
 
202
      if (size == 0) {
 
203
        return BigInteger.Zero;
 
204
      }
 
205
 
 
206
      UInt32[] array = new UInt32[size];
 
207
      array[0] = (UInt32)bits[0];
 
208
      if (size > 1) array[1] = (UInt32)bits[1];
 
209
      if (size > 2) array[2] = (UInt32)bits[2];
 
210
 
 
211
      return new BigInteger(((bits[3] & DecimalSignMask) != 0) ? -1 : +1, array);
 
212
    }
 
213
 
 
214
    /// <summary>
 
215
    /// Create a BigInteger from a little-endian twos-complement byte array
 
216
    /// (inverse of ToByteArray())
 
217
    /// </summary>
 
218
    public static BigInteger Create(byte[] v) {
 
219
      //Contract.RequiresNotNull(v, "v");
 
220
      if (v.Length == 0) return Create(0);
 
221
 
 
222
      int byteCount = v.Length;
 
223
      int unalignedBytes = byteCount % 4;
 
224
      int dwordCount = byteCount / 4 + (unalignedBytes == 0 ? 0 : 1);
 
225
      uint[] data = new uint[dwordCount];
 
226
 
 
227
      bool isNegative = (v[byteCount - 1] & 0x80) == 0x80;
 
228
 
 
229
      bool isZero = true;
 
230
 
 
231
      // Copy all dwords, except but don't do the last one if it's not a full four bytes
 
232
      int curDword, curByte, byteInDword;
 
233
      curByte = 3;
 
234
      for (curDword = 0; curDword < dwordCount - (unalignedBytes == 0 ? 0 : 1); curDword++) {
 
235
        byteInDword = 0;
 
236
        while (byteInDword < 4) {
 
237
          if (v[curByte] != 0x00) isZero = false;
 
238
          data[curDword] <<= 8;
 
239
          data[curDword] |= v[curByte];
 
240
          curByte--;
 
241
          byteInDword++;
 
242
        }
 
243
        curByte += 8;
 
244
      }
 
245
 
 
246
      // Copy the last dword specially if it's not aligned
 
247
      if (unalignedBytes != 0) {
 
248
        if (isNegative) data[dwordCount - 1] = 0xffffffff;
 
249
        for (curByte = byteCount - 1; curByte >= byteCount - unalignedBytes; curByte--) {
 
250
          if (v[curByte] != 0x00) isZero = false;
 
251
          data[curDword] <<= 8;
 
252
          data[curDword] |= v[curByte];
 
253
        }
 
254
      }
 
255
 
 
256
      if (isZero) return Zero;
 
257
 
 
258
      if (isNegative) {
 
259
        makeTwosComplement(data);
 
260
        return new BigInteger(-1, data);
 
261
      }
 
262
      return new BigInteger(1, data);
 
263
    }
 
264
 
 
265
 
 
266
    private static bool Negative(byte[] v) {
 
267
      return ((v[7] & 0x80) != 0);
 
268
    }
 
269
 
 
270
    private static ushort Exponent(byte[] v) {
 
271
      return (ushort)((((ushort)(v[7] & 0x7F)) << (ushort)4) | (((ushort)(v[6] & 0xF0)) >> 4));
 
272
    }
 
273
 
 
274
    private static ulong Mantissa(byte[] v) {
 
275
      uint i1 = ((uint)v[0] | ((uint)v[1] << 8) | ((uint)v[2] << 16) | ((uint)v[3] << 24));
 
276
      uint i2 = ((uint)v[4] | ((uint)v[5] << 8) | ((uint)(v[6] & 0xF) << 16));
 
277
 
 
278
      return (ulong)((ulong)i1 | ((ulong)i2 << 32));
 
279
    }
 
280
 
 
281
    private const int bias = 1075; //RI: changed from static field to const, to avoid security warning
 
282
    public static BigInteger Create(double v) {
 
283
      byte[] bytes = System.BitConverter.GetBytes(v);
 
284
      ulong mantissa = Mantissa(bytes);
 
285
      if (mantissa == 0) {
 
286
        // 1.0 * 2**exp, we have a power of 2
 
287
        int exponent = Exponent(bytes);
 
288
        if (exponent == 0) return Zero;
 
289
 
 
290
        BigInteger res = Negative(bytes) ? Negate(One) : One;
 
291
        res = res << (exponent - 0x3ff);
 
292
        return res;
 
293
      } else {
 
294
        // 1.mantissa * 2**exp
 
295
        int exponent = Exponent(bytes);
 
296
        mantissa |= 0x10000000000000ul;
 
297
        BigInteger res = BigInteger.Create(mantissa);
 
298
        res = exponent > bias ? res << (exponent - bias) : res >> (bias - exponent);
 
299
        return Negative(bytes) ? res * (-1) : res;
 
300
      }
 
301
    }
 
302
 
 
303
    public static implicit operator BigInteger(byte i) {
 
304
      return Create((uint)i);
 
305
    }
 
306
 
 
307
    [CLSCompliant(false)]
 
308
    public static implicit operator BigInteger(sbyte i) {
 
309
      return Create((int)i);
 
310
    }
 
311
 
 
312
    public static implicit operator BigInteger(short i) {
 
313
      return Create((int)i);
 
314
    }
 
315
 
 
316
    [CLSCompliant(false)]
 
317
    public static implicit operator BigInteger(ushort i) {
 
318
      return Create((uint)i);
 
319
    }
 
320
 
 
321
    [CLSCompliant(false)]
 
322
    public static implicit operator BigInteger(uint i) {
 
323
      return Create(i);
 
324
    }
 
325
 
 
326
    public static implicit operator BigInteger(int i) {
 
327
      return Create(i);
 
328
    }
 
329
 
 
330
    [CLSCompliant(false)]
 
331
    public static implicit operator BigInteger(ulong i) {
 
332
      return Create(i);
 
333
    }
 
334
 
 
335
    public static implicit operator BigInteger(long i) {
 
336
      return Create(i);
 
337
    }
 
338
 
 
339
    public static implicit operator BigInteger(decimal i) {
 
340
      return Create(i);
 
341
    }
 
342
 
 
343
    public static implicit operator double(BigInteger i) {
 
344
      if (object.ReferenceEquals(i, null)) {
 
345
        throw new ArgumentNullException("i");
 
346
      }
 
347
      return i.ToFloat64();
 
348
    }
 
349
 
 
350
    public static explicit operator byte(BigInteger self) {
 
351
      int tmp;
 
352
      if (self.AsInt32(out tmp)) {
 
353
        return checked((byte)tmp);
 
354
      }
 
355
      throw new OverflowException();
 
356
    }
 
357
 
 
358
    [CLSCompliant(false)]
 
359
    public static explicit operator sbyte(BigInteger self) {
 
360
      int tmp;
 
361
      if (self.AsInt32(out tmp)) {
 
362
        return checked((sbyte)tmp);
 
363
      }
 
364
      throw new OverflowException();
 
365
    }
 
366
 
 
367
    [CLSCompliant(false)]
 
368
    public static explicit operator UInt16(BigInteger self) {
 
369
      int tmp;
 
370
      if (self.AsInt32(out tmp)) {
 
371
        return checked((UInt16)tmp);
 
372
      }
 
373
      throw new OverflowException();
 
374
    }
 
375
 
 
376
    public static explicit operator Int16(BigInteger self) {
 
377
      int tmp;
 
378
      if (self.AsInt32(out tmp)) {
 
379
        return checked((Int16)tmp);
 
380
      }
 
381
      throw new OverflowException();
 
382
    }
 
383
 
 
384
    [CLSCompliant(false)]
 
385
    public static explicit operator UInt32(BigInteger self) {
 
386
      uint tmp;
 
387
      if (self.AsUInt32(out tmp)) {
 
388
        return tmp;
 
389
      }
 
390
      throw new OverflowException();
 
391
    }
 
392
 
 
393
    public static explicit operator Int32(BigInteger self) {
 
394
      int tmp;
 
395
      if (self.AsInt32(out tmp)) {
 
396
        return tmp;
 
397
      }
 
398
      throw new OverflowException();
 
399
    }
 
400
 
 
401
    public static explicit operator Int64(BigInteger self) {
 
402
      long tmp;
 
403
      if (self.AsInt64(out tmp)) {
 
404
        return tmp;
 
405
      }
 
406
      throw new OverflowException();
 
407
    }
 
408
 
 
409
    [CLSCompliant(false)]
 
410
    public static explicit operator UInt64(BigInteger self) {
 
411
      ulong tmp;
 
412
      if (self.AsUInt64(out tmp)) {
 
413
        return tmp;
 
414
      }
 
415
      throw new OverflowException();
 
416
    }
 
417
 
 
418
    public static explicit operator float(BigInteger self) {
 
419
      if (object.ReferenceEquals(self, null)) {
 
420
        throw new ArgumentNullException("self");
 
421
      }
 
422
      return checked((float)self.ToFloat64());
 
423
    }
 
424
 
 
425
    public static explicit operator decimal(BigInteger self) {
 
426
      decimal res;
 
427
      if (self.AsDecimal(out res)) {
 
428
        return res;
 
429
      }
 
430
      throw new OverflowException();
 
431
    }
 
432
 
 
433
    public BigInteger(BigInteger copy) {
 
434
      if (object.ReferenceEquals(copy, null)) {
 
435
        throw new ArgumentNullException("copy");
 
436
      }
 
437
      this.sign = copy.sign;
 
438
      this.data = copy.data;
 
439
    }
 
440
 
 
441
    [CLSCompliant(false)]
 
442
    public BigInteger(int sign, params uint[] data) {
 
443
      //Contract.RequiresNotNull(data, "data");
 
444
      if (sign != -1 && sign != 0 && sign != 1) throw new ArgumentException(MathResources.InvalidArgument, "sign");
 
445
      if (GetLength(data) != 0) {
 
446
        if (sign == 0) throw new ArgumentException(MathResources.InvalidArgument, "sign");
 
447
      } else sign = 0;
 
448
 
 
449
      this.data = data;
 
450
      this.sign = (short)sign;
 
451
    }
 
452
 
 
453
    /// <summary>
 
454
    /// Return the magnitude of this BigInteger as an array of zero or more uints.
 
455
    /// Element zero is the value of the least significant four bytes, element one is
 
456
    /// the value of the four next most significant bytes, etc.
 
457
    /// 
 
458
    /// The returned data is the unsigned magnitude of the number. To determine the sign,
 
459
    /// use GetSign().
 
460
    /// 
 
461
    /// It is guaranteed that the highest element of the returned array is never zero.
 
462
    /// This means that if the value of this BigInteger is zero, a zero-length array
 
463
    /// is returned.
 
464
    /// </summary>
 
465
    [CLSCompliant(false)]
 
466
    public uint[] GetBits() {
 
467
      if (sign == 0) return new uint[0];
 
468
      int mostSignificantNonZeroWord;
 
469
      for (
 
470
          mostSignificantNonZeroWord = data.Length - 1;
 
471
          mostSignificantNonZeroWord >= 0 && data[mostSignificantNonZeroWord] == 0;
 
472
          mostSignificantNonZeroWord--
 
473
      ) ;
 
474
      uint[] bits = new uint[mostSignificantNonZeroWord + 1];
 
475
      Array.Copy(data, bits, mostSignificantNonZeroWord + 1);
 
476
      return bits;
 
477
    }
 
478
 
 
479
    /// <summary>
 
480
    /// Return the sign of this BigInteger: -1, 0, or 1.
 
481
    /// </summary>
 
482
    public short Sign {
 
483
      get {
 
484
        return sign;
 
485
      }
 
486
    }
 
487
 
 
488
    public bool AsInt64(out long ret) {
 
489
      ret = 0;
 
490
      if (sign == 0) return true;
 
491
      if (Length > 2) return false;
 
492
      if (data.Length == 1) {
 
493
        ret = sign * (long)data[0];
 
494
        return true;
 
495
      }
 
496
      ulong tmp = (((ulong)data[1]) << 32 | (ulong)data[0]);
 
497
      if (tmp > 0x8000000000000000) return false;
 
498
      if (tmp == 0x8000000000000000 && sign == 1) return false;
 
499
      ret = ((long)tmp) * sign;
 
500
      return true;
 
501
    }
 
502
 
 
503
    [CLSCompliant(false)]
 
504
    public bool AsUInt32(out uint ret) {
 
505
      ret = 0;
 
506
      if (sign == 0) return true;
 
507
      if (sign < 0) return false;
 
508
      if (Length > 1) return false;
 
509
      ret = data[0];
 
510
      return true;
 
511
    }
 
512
 
 
513
    [CLSCompliant(false)]
 
514
    public bool AsUInt64(out ulong ret) {
 
515
      ret = 0;
 
516
      if (sign == 0) return true;
 
517
      if (sign < 0) return false;
 
518
      if (Length > 2) return false;
 
519
      ret = (ulong)data[0];
 
520
      if (data.Length > 1) {
 
521
        ret |= ((ulong)data[1]) << 32;
 
522
      }
 
523
      return true;
 
524
    }
 
525
 
 
526
    public bool AsInt32(out int ret) {
 
527
      ret = 0;
 
528
      if (sign == 0) return true;
 
529
      if (Length > 1) return false;
 
530
      if (data[0] > 0x80000000) return false;
 
531
      if (data[0] == 0x80000000 && sign == 1) return false;
 
532
      ret = (int)data[0];
 
533
      ret *= sign;
 
534
      return true;
 
535
    }
 
536
 
 
537
    public bool AsDecimal(out Decimal ret) {
 
538
      if (sign == 0) {
 
539
        ret = Decimal.Zero;
 
540
        return true;
 
541
      }
 
542
 
 
543
      BigInteger bi = this;
 
544
 
 
545
      int scale = 0;
 
546
      int length = Length;
 
547
      while (length > 3) {
 
548
        if (scale >= 28) {
 
549
          ret = default(decimal);
 
550
          return false;
 
551
        }
 
552
        bi = bi / 10;
 
553
        scale++;
 
554
 
 
555
        length = bi.Length;
 
556
      }
 
557
 
 
558
      int lo = 0, mi = 0, hi = 0;
 
559
      if (length > 2) hi = (Int32)bi.data[2];
 
560
      if (length > 1) mi = (Int32)bi.data[1];
 
561
      if (length > 0) lo = (Int32)bi.data[0];
 
562
 
 
563
      ret = new Decimal(lo, mi, hi, sign < 0, (byte)scale);
 
564
      return true;
 
565
    }
 
566
 
 
567
 
 
568
    [CLSCompliant(false)]
 
569
    public uint ToUInt32() {
 
570
      uint ret;
 
571
      if (AsUInt32(out ret)) return ret;
 
572
      throw new OverflowException(MathResources.BigIntWontFitUInt);
 
573
    }
 
574
 
 
575
    public int ToInt32() {
 
576
      int ret;
 
577
      if (AsInt32(out ret)) return ret;
 
578
      throw new OverflowException(MathResources.BigIntWontFitInt);
 
579
    }
 
580
 
 
581
    public decimal ToDecimal() {
 
582
      decimal ret;
 
583
      if (AsDecimal(out ret)) return ret;
 
584
      throw new OverflowException(MathResources.BigIntWontFitDecimal);
 
585
    }
 
586
 
 
587
    [CLSCompliant(false)]
 
588
    public ulong ToUInt64() {
 
589
      ulong ret;
 
590
      if (AsUInt64(out ret)) return ret;
 
591
      throw new OverflowException(MathResources.BigIntWontFitULong);
 
592
    }
 
593
 
 
594
    public long ToInt64() {
 
595
      long ret;
 
596
      if (AsInt64(out ret)) return ret;
 
597
      throw new OverflowException(MathResources.BigIntWontFitLong);
 
598
    }
 
599
 
 
600
    public bool TryToFloat64(out double result) {
 
601
      return double.TryParse(ToString(10),
 
602
          System.Globalization.NumberStyles.Number,
 
603
          System.Globalization.CultureInfo.InvariantCulture.NumberFormat,
 
604
          out result);
 
605
    }
 
606
 
 
607
    public double ToFloat64() {
 
608
      return double.Parse(
 
609
          ToString(10),
 
610
          System.Globalization.CultureInfo.InvariantCulture.NumberFormat
 
611
          );
 
612
    }
 
613
 
 
614
    public int Length {
 
615
      get {
 
616
        return GetLength(data);
 
617
      }
 
618
    }
 
619
 
 
620
    private static int GetLength(uint[] data) {
 
621
      int ret = data.Length - 1;
 
622
      while (ret >= 0 && data[ret] == 0) ret--;
 
623
      return ret + 1;
 
624
    }
 
625
 
 
626
 
 
627
    private static uint[] copy(uint[] v) {
 
628
      uint[] ret = new uint[v.Length];
 
629
      Array.Copy(v, ret, v.Length);
 
630
      return ret;
 
631
    }
 
632
 
 
633
    private static uint[] resize(uint[] v, int len) {
 
634
      if (v.Length == len) return v;
 
635
      uint[] ret = new uint[len];
 
636
      int n = System.Math.Min(v.Length, len);
 
637
      for (int i = 0; i < n; i++) {
 
638
        ret[i] = v[i];
 
639
      }
 
640
      return ret;
 
641
    }
 
642
 
 
643
    private static uint[] InternalAdd(uint[] x, int xl, uint[] y, int yl) {
 
644
      Debug.Assert(xl >= yl);
 
645
      uint[] z = new uint[xl];
 
646
 
 
647
      int i;
 
648
      ulong sum = 0;
 
649
      for (i = 0; i < yl; i++) {
 
650
        sum = sum + x[i] + y[i];
 
651
        z[i] = (uint)sum;
 
652
        sum >>= BitsPerDigit;
 
653
      }
 
654
 
 
655
      for (; i < xl && sum != 0; i++) {
 
656
        sum = sum + x[i];
 
657
        z[i] = (uint)sum;
 
658
        sum >>= BitsPerDigit;
 
659
      }
 
660
      if (sum != 0) {
 
661
        z = resize(z, xl + 1);
 
662
        z[i] = (uint)sum;
 
663
      } else {
 
664
        for (; i < xl; i++) {
 
665
          z[i] = x[i];
 
666
        }
 
667
      }
 
668
      return z;
 
669
    }
 
670
 
 
671
    private static uint[] sub(uint[] x, int xl, uint[] y, int yl) {
 
672
      Debug.Assert(xl >= yl);
 
673
      uint[] z = new uint[xl];
 
674
 
 
675
      int i;
 
676
      bool borrow = false;
 
677
      for (i = 0; i < yl; i++) {
 
678
        uint xi = x[i];
 
679
        uint yi = y[i];
 
680
        if (borrow) {
 
681
          if (xi == 0) {
 
682
            xi = 0xffffffff;
 
683
            borrow = true;
 
684
          } else {
 
685
            xi -= 1;
 
686
            borrow = false;
 
687
          }
 
688
        }
 
689
        if (yi > xi) borrow = true;
 
690
        z[i] = xi - yi;
 
691
      }
 
692
 
 
693
      if (borrow) {
 
694
        for (; i < xl; i++) {
 
695
          uint xi = x[i];
 
696
          z[i] = xi - 1;
 
697
          if (xi != 0) { i++; break; }
 
698
        }
 
699
      }
 
700
      for (; i < xl; i++) {
 
701
        z[i] = x[i];
 
702
      }
 
703
      return z;  // may have leading zeros
 
704
    }
 
705
 
 
706
    private static uint[] add0(uint[] x, int xl, uint[] y, int yl) {
 
707
      if (xl >= yl) return InternalAdd(x, xl, y, yl);
 
708
      else return InternalAdd(y, yl, x, xl);
 
709
    }
 
710
 
 
711
    public static int Compare(BigInteger x, BigInteger y) {
 
712
      if (object.ReferenceEquals(x, null)) {
 
713
        throw new ArgumentNullException("x");
 
714
      }
 
715
      if (object.ReferenceEquals(y, null)) {
 
716
        throw new ArgumentNullException("y");
 
717
      }
 
718
      if (x.sign == y.sign) {
 
719
        int xl = x.Length;
 
720
        int yl = y.Length;
 
721
        if (xl == yl) {
 
722
          for (int i = xl - 1; i >= 0; i--) {
 
723
            if (x.data[i] == y.data[i]) continue;
 
724
            return x.data[i] > y.data[i] ? x.sign : -x.sign;
 
725
          }
 
726
          return 0;
 
727
        } else {
 
728
          return xl > yl ? +x.sign : -x.sign;
 
729
        }
 
730
      } else {
 
731
        return x.sign > y.sign ? +1 : -1;
 
732
      }
 
733
    }
 
734
 
 
735
    public static bool operator ==(BigInteger x, int y) {
 
736
      return x == (BigInteger)y;
 
737
    }
 
738
 
 
739
    public static bool operator !=(BigInteger x, int y) {
 
740
      return !(x == y);
 
741
    }
 
742
 
 
743
    public static bool operator ==(BigInteger x, double y) {
 
744
      if (object.ReferenceEquals(x, null)) {
 
745
        throw new ArgumentNullException("x");
 
746
      }
 
747
 
 
748
      // we can hold all double values, but not all double values
 
749
      // can hold BigInteger values, and we may lose precision.  Convert
 
750
      // the double to a big int, then compare.
 
751
 
 
752
      if ((y % 1) != 0) return false;  // not a whole number, can't be equal
 
753
 
 
754
      return x == BigInteger.Create(y);
 
755
    }
 
756
 
 
757
    public static bool operator ==(double x, BigInteger y) {
 
758
      return y == x;
 
759
    }
 
760
 
 
761
    public static bool operator !=(BigInteger x, double y) {
 
762
      return !(x == y);
 
763
    }
 
764
 
 
765
    public static bool operator !=(double x, BigInteger y) {
 
766
      return !(x == y);
 
767
    }
 
768
 
 
769
 
 
770
    public static bool operator ==(BigInteger x, BigInteger y) {
 
771
      return Compare(x, y) == 0;
 
772
    }
 
773
 
 
774
    public static bool operator !=(BigInteger x, BigInteger y) {
 
775
      return Compare(x, y) != 0;
 
776
    }
 
777
    public static bool operator <(BigInteger x, BigInteger y) {
 
778
      return Compare(x, y) < 0;
 
779
    }
 
780
    public static bool operator <=(BigInteger x, BigInteger y) {
 
781
      return Compare(x, y) <= 0;
 
782
    }
 
783
    public static bool operator >(BigInteger x, BigInteger y) {
 
784
      return Compare(x, y) > 0;
 
785
    }
 
786
    public static bool operator >=(BigInteger x, BigInteger y) {
 
787
      return Compare(x, y) >= 0;
 
788
    }
 
789
 
 
790
    public static BigInteger Add(BigInteger x, BigInteger y) {
 
791
      return x + y;
 
792
    }
 
793
 
 
794
    public static BigInteger operator +(BigInteger x, BigInteger y) {
 
795
      if (object.ReferenceEquals(x, null)) {
 
796
        throw new ArgumentNullException("x");
 
797
      }
 
798
      if (object.ReferenceEquals(y, null)) {
 
799
        throw new ArgumentNullException("y");
 
800
      }
 
801
 
 
802
      if (x.sign == y.sign) {
 
803
        return new BigInteger(x.sign, add0(x.data, x.Length, y.data, y.Length));
 
804
      } else {
 
805
        return x - new BigInteger(-y.sign, y.data);  //??? performance issue
 
806
      }
 
807
    }
 
808
 
 
809
    public static BigInteger Subtract(BigInteger x, BigInteger y) {
 
810
      return x - y;
 
811
    }
 
812
 
 
813
    public static BigInteger operator -(BigInteger x, BigInteger y) {
 
814
      int c = Compare(x, y);
 
815
      if (c == 0) return Zero;
 
816
 
 
817
      if (x.sign == y.sign) {
 
818
        uint[] z;
 
819
        switch (c * x.sign) {
 
820
          case +1:
 
821
            z = sub(x.data, x.Length, y.data, y.Length);
 
822
            break;
 
823
          case -1:
 
824
            z = sub(y.data, y.Length, x.data, x.Length);
 
825
            break;
 
826
          default:
 
827
            return Zero;
 
828
        }
 
829
        return new BigInteger(c, z);
 
830
      } else {
 
831
        uint[] z = add0(x.data, x.Length, y.data, y.Length);
 
832
        return new BigInteger(c, z);
 
833
      }
 
834
    }
 
835
 
 
836
    public static BigInteger Multiply(BigInteger x, BigInteger y) {
 
837
      return x * y;
 
838
    }
 
839
 
 
840
    public static BigInteger operator *(BigInteger x, BigInteger y) {
 
841
      if (object.ReferenceEquals(x, null)) {
 
842
        throw new ArgumentNullException("x");
 
843
      }
 
844
      if (object.ReferenceEquals(y, null)) {
 
845
        throw new ArgumentNullException("y");
 
846
      }
 
847
      int xl = x.Length;
 
848
      int yl = y.Length;
 
849
      int zl = xl + yl;
 
850
      uint[] xd = x.data, yd = y.data, zd = new uint[zl];
 
851
 
 
852
      for (int xi = 0; xi < xl; xi++) {
 
853
        uint xv = xd[xi];
 
854
        int zi = xi;
 
855
        ulong carry = 0;
 
856
        for (int yi = 0; yi < yl; yi++) {
 
857
          carry = carry + ((ulong)xv) * yd[yi] + zd[zi];
 
858
          zd[zi++] = (uint)carry;
 
859
          carry >>= BitsPerDigit;
 
860
        }
 
861
        while (carry != 0) {
 
862
          carry += zd[zi];
 
863
          zd[zi++] = (uint)carry;
 
864
          carry >>= BitsPerDigit;
 
865
        }
 
866
      }
 
867
 
 
868
      return new BigInteger(x.sign * y.sign, zd);
 
869
    }
 
870
 
 
871
    public static BigInteger Divide(BigInteger x, BigInteger y) {
 
872
      return x / y;
 
873
    }
 
874
 
 
875
    public static BigInteger operator /(BigInteger x, BigInteger y) {
 
876
      BigInteger dummy;
 
877
      return DivRem(x, y, out dummy);
 
878
    }
 
879
 
 
880
    public static BigInteger Mod(BigInteger x, BigInteger y) {
 
881
      return x % y;
 
882
    }
 
883
 
 
884
    public static BigInteger operator %(BigInteger x, BigInteger y) {
 
885
      BigInteger ret;
 
886
      DivRem(x, y, out ret);
 
887
      return ret;
 
888
    }
 
889
 
 
890
    private static int GetNormalizeShift(uint value) {
 
891
      int shift = 0;
 
892
 
 
893
      if ((value & 0xFFFF0000) == 0) { value <<= 16; shift += 16; }
 
894
      if ((value & 0xFF000000) == 0) { value <<= 8; shift += 8; }
 
895
      if ((value & 0xF0000000) == 0) { value <<= 4; shift += 4; }
 
896
      if ((value & 0xC0000000) == 0) { value <<= 2; shift += 2; }
 
897
      if ((value & 0x80000000) == 0) { value <<= 1; shift += 1; }
 
898
 
 
899
      return shift;
 
900
    }
 
901
 
 
902
    [Conditional("DEBUG")]
 
903
    [SuppressMessage("Microsoft.Usage", "CA1806:DoNotIgnoreMethodResults", MessageId = "Microsoft.Scripting.Math.BigInteger")]
 
904
    private static void TestNormalize(uint[] u, uint[] un, int shift) {
 
905
      BigInteger i = new BigInteger(1, u);
 
906
      BigInteger j = new BigInteger(1, un);
 
907
      BigInteger k = j >> shift;
 
908
 
 
909
      Debug.Assert(i == k);
 
910
    }
 
911
 
 
912
    [Conditional("DEBUG")]
 
913
    private static void TestDivisionStep(uint[] un, uint[] vn, uint[] q, uint[] u, uint[] v) {
 
914
      int n = GetLength(v);
 
915
      int shift = GetNormalizeShift(v[n - 1]);
 
916
 
 
917
      BigInteger uni = new BigInteger(1, un);
 
918
      BigInteger vni = new BigInteger(1, vn);
 
919
      BigInteger qi = new BigInteger(1, q);
 
920
      BigInteger ui = new BigInteger(1, u);
 
921
 
 
922
      BigInteger expected = vni * qi + uni;
 
923
      BigInteger usi = ui << shift;
 
924
 
 
925
      Debug.Assert(expected == usi);
 
926
    }
 
927
 
 
928
    [Conditional("DEBUG")]
 
929
    [SuppressMessage("Microsoft.Usage", "CA1806:DoNotIgnoreMethodResults", MessageId = "Microsoft.Scripting.Math.BigInteger")]
 
930
    private static void TestResult(uint[] u, uint[] v, uint[] q, uint[] r) {
 
931
      BigInteger ui = new BigInteger(1, u);
 
932
      BigInteger vi = new BigInteger(1, v);
 
933
      BigInteger qi = new BigInteger(1, q);
 
934
      BigInteger ri = new BigInteger(1, r);
 
935
 
 
936
      BigInteger viqi = vi * qi;
 
937
      BigInteger expected = viqi + ri;
 
938
      Debug.Assert(ui == expected);
 
939
      Debug.Assert(ri < vi);
 
940
    }
 
941
 
 
942
    private static void Normalize(uint[] u, int l, uint[] un, int shift) {
 
943
      Debug.Assert(un.Length == l || un.Length == l + 1);
 
944
      Debug.Assert(un.Length == l + 1 || ((u[l - 1] << shift) >> shift) == u[l - 1]);
 
945
      Debug.Assert(0 <= shift && shift < 32);
 
946
 
 
947
      uint carry = 0;
 
948
      int i;
 
949
      if (shift > 0) {
 
950
        int rshift = BitsPerDigit - shift;
 
951
        for (i = 0; i < l; i++) {
 
952
          uint ui = u[i];
 
953
          un[i] = (ui << shift) | carry;
 
954
          carry = ui >> rshift;
 
955
        }
 
956
      } else {
 
957
        for (i = 0; i < l; i++) {
 
958
          un[i] = u[i];
 
959
        }
 
960
      }
 
961
 
 
962
      while (i < un.Length) {
 
963
        un[i++] = 0;
 
964
      }
 
965
 
 
966
      if (carry != 0) {
 
967
        Debug.Assert(l == un.Length - 1);
 
968
        un[l] = carry;
 
969
      }
 
970
 
 
971
      TestNormalize(u, un, shift);
 
972
    }
 
973
 
 
974
    private static void Unnormalize(uint[] un, out uint[] r, int shift) {
 
975
      Debug.Assert(0 <= shift && shift < 32);
 
976
 
 
977
      int length = GetLength(un);
 
978
      r = new uint[length];
 
979
 
 
980
      if (shift > 0) {
 
981
        int lshift = 32 - shift;
 
982
        uint carry = 0;
 
983
        for (int i = length - 1; i >= 0; i--) {
 
984
          uint uni = un[i];
 
985
          r[i] = (uni >> shift) | carry;
 
986
          carry = (uni << lshift);
 
987
        }
 
988
      } else {
 
989
        for (int i = 0; i < length; i++) {
 
990
          r[i] = un[i];
 
991
        }
 
992
      }
 
993
 
 
994
      TestNormalize(r, un, shift);
 
995
    }
 
996
 
 
997
    private static void DivModUnsigned(uint[] u, uint[] v, out uint[] q, out uint[] r) {
 
998
      int m = GetLength(u);
 
999
      int n = GetLength(v);
 
1000
 
 
1001
      if (n <= 1) {
 
1002
        if (n == 0) {
 
1003
          throw new DivideByZeroException();
 
1004
        }
 
1005
 
 
1006
        //  Divide by single digit
 
1007
        //
 
1008
        ulong rem = 0;
 
1009
        uint v0 = v[0];
 
1010
        q = new uint[m];
 
1011
        r = new uint[1];
 
1012
 
 
1013
        for (int j = m - 1; j >= 0; j--) {
 
1014
          rem *= Base;
 
1015
          rem += u[j];
 
1016
 
 
1017
          ulong div = rem / v0;
 
1018
          rem -= div * v0;
 
1019
          q[j] = (uint)div;
 
1020
        }
 
1021
        r[0] = (uint)rem;
 
1022
      } else if (m >= n) {
 
1023
        int shift = GetNormalizeShift(v[n - 1]);
 
1024
 
 
1025
        uint[] un = new uint[m + 1];
 
1026
        uint[] vn = new uint[n];
 
1027
 
 
1028
        Normalize(u, m, un, shift);
 
1029
        Normalize(v, n, vn, shift);
 
1030
 
 
1031
        q = new uint[m - n + 1];
 
1032
        r = null;
 
1033
 
 
1034
        TestDivisionStep(un, vn, q, u, v);
 
1035
 
 
1036
        //  Main division loop
 
1037
        //
 
1038
        for (int j = m - n; j >= 0; j--) {
 
1039
          ulong rr, qq;
 
1040
          int i;
 
1041
 
 
1042
          rr = Base * un[j + n] + un[j + n - 1];
 
1043
          qq = rr / vn[n - 1];
 
1044
          rr -= qq * vn[n - 1];
 
1045
 
 
1046
          Debug.Assert((Base * un[j + n] + un[j + n - 1]) == qq * vn[n - 1] + rr);
 
1047
 
 
1048
          for (; ; ) {
 
1049
            // Estimate too big ?
 
1050
            //
 
1051
            if ((qq >= Base) || (qq * vn[n - 2] > (rr * Base + un[j + n - 2]))) {
 
1052
              qq--;
 
1053
              rr += (ulong)vn[n - 1];
 
1054
              if (rr < Base) continue;
 
1055
            }
 
1056
            break;
 
1057
          }
 
1058
 
 
1059
          Debug.Assert((Base * un[j + n] + un[j + n - 1]) == qq * vn[n - 1] + rr);
 
1060
 
 
1061
          //  Multiply and subtract
 
1062
          //
 
1063
          long b = 0;
 
1064
          long t = 0;
 
1065
          for (i = 0; i < n; i++) {
 
1066
            ulong p = vn[i] * qq;
 
1067
            t = (long)un[i + j] - (long)(uint)p - b;
 
1068
            un[i + j] = (uint)t;
 
1069
            p >>= 32;
 
1070
            t >>= 32;
 
1071
            Debug.Assert(t == 0 || t == -1 || t == -2);
 
1072
            b = (long)p - t;
 
1073
          }
 
1074
          t = (long)un[j + n] - b;
 
1075
          un[j + n] = (uint)t;
 
1076
 
 
1077
          //  Store the calculated value
 
1078
          //
 
1079
          q[j] = (uint)qq;
 
1080
 
 
1081
          //  Add back vn[0..n] to un[j..j+n]
 
1082
          //
 
1083
          if (t < 0) {
 
1084
            q[j]--;
 
1085
            ulong c = 0;
 
1086
            for (i = 0; i < n; i++) {
 
1087
              c = (ulong)vn[i] + un[j + i] + c;
 
1088
              un[j + i] = (uint)c;
 
1089
              c >>= 32;
 
1090
            }
 
1091
            c += (ulong)un[j + n];
 
1092
            un[j + n] = (uint)c;
 
1093
          }
 
1094
 
 
1095
          TestDivisionStep(un, vn, q, u, v);
 
1096
        }
 
1097
 
 
1098
        Unnormalize(un, out r, shift);
 
1099
 
 
1100
        //  Test normalized value ... Call TestNormalize
 
1101
        //  only pass the values in different order.
 
1102
        //
 
1103
        TestNormalize(r, un, shift);
 
1104
      } else {
 
1105
        q = new uint[] { 0 };
 
1106
        r = u;
 
1107
      }
 
1108
 
 
1109
      TestResult(u, v, q, r);
 
1110
    }
 
1111
 
 
1112
    public static BigInteger DivRem(BigInteger x, BigInteger y, out BigInteger remainder) {
 
1113
      if (object.ReferenceEquals(x, null)) {
 
1114
        throw new ArgumentNullException("x");
 
1115
      }
 
1116
      if (object.ReferenceEquals(y, null)) {
 
1117
        throw new ArgumentNullException("y");
 
1118
      }
 
1119
 
 
1120
      uint[] q;
 
1121
      uint[] r;
 
1122
 
 
1123
      DivModUnsigned(x.data, y.data, out q, out r);
 
1124
 
 
1125
      remainder = new BigInteger(x.sign, r);
 
1126
      return new BigInteger(x.sign * y.sign, q);
 
1127
    }
 
1128
 
 
1129
    private static uint div(uint[] n, ref int nl, uint d) {
 
1130
      ulong rem = 0;
 
1131
      int i = nl;
 
1132
      bool seenNonZero = false;
 
1133
      while (--i >= 0) {
 
1134
        rem <<= BitsPerDigit;
 
1135
        rem |= n[i];
 
1136
        uint v = (uint)(rem / d);
 
1137
        n[i] = v;
 
1138
        if (v == 0) {
 
1139
          if (!seenNonZero) nl--;
 
1140
        } else {
 
1141
          seenNonZero = true;
 
1142
        }
 
1143
        rem %= d;
 
1144
      }
 
1145
      return (uint)rem;
 
1146
    }
 
1147
 
 
1148
    private static uint extend(uint v, ref bool seenNonZero) {
 
1149
      if (seenNonZero) {
 
1150
        return ~v;
 
1151
      } else {
 
1152
        if (v == 0) {
 
1153
          return 0;
 
1154
        } else {
 
1155
          seenNonZero = true;
 
1156
          return ~v + 1;
 
1157
        }
 
1158
      }
 
1159
    }
 
1160
 
 
1161
    private static uint getOne(bool isNeg, uint[] data, int i, ref bool seenNonZero) {
 
1162
      if (i < data.Length) {
 
1163
        uint ret = data[i];
 
1164
        return isNeg ? extend(ret, ref seenNonZero) : ret;
 
1165
      } else {
 
1166
        return isNeg ? uint.MaxValue : 0;
 
1167
      }
 
1168
    }
 
1169
 
 
1170
    /// <summary>
 
1171
    /// Do an in-place twos complement of d and also return the result.
 
1172
    /// </summary>
 
1173
    private static uint[] makeTwosComplement(uint[] d) {
 
1174
      // first do complement and +1 as long as carry is needed
 
1175
      int i = 0;
 
1176
      uint v = 0;
 
1177
      for (; i < d.Length; i++) {
 
1178
        v = ~d[i] + 1;
 
1179
        d[i] = v;
 
1180
        if (v != 0) { i++; break; }
 
1181
      }
 
1182
 
 
1183
      if (v != 0) {
 
1184
        // now ones complement is sufficient
 
1185
        for (; i < d.Length; i++) {
 
1186
          d[i] = ~d[i];
 
1187
        }
 
1188
      } else {
 
1189
        //??? this is weird
 
1190
        d = resize(d, d.Length + 1);
 
1191
        d[d.Length - 1] = 1;
 
1192
      }
 
1193
      return d;
 
1194
    }
 
1195
 
 
1196
    public static BigInteger BitwiseAnd(BigInteger x, BigInteger y) {
 
1197
      return x & y;
 
1198
    }
 
1199
 
 
1200
    public static BigInteger operator &(BigInteger x, BigInteger y) {
 
1201
      if (object.ReferenceEquals(x, null)) {
 
1202
        throw new ArgumentNullException("x");
 
1203
      }
 
1204
      if (object.ReferenceEquals(y, null)) {
 
1205
        throw new ArgumentNullException("y");
 
1206
      }
 
1207
      int xl = x.Length, yl = y.Length;
 
1208
      uint[] xd = x.data, yd = y.data;
 
1209
 
 
1210
      int zl = System.Math.Max(xl, yl);
 
1211
      uint[] zd = new uint[zl];
 
1212
 
 
1213
      bool negx = x.sign == -1, negy = y.sign == -1;
 
1214
      bool seenNonZeroX = false, seenNonZeroY = false;
 
1215
      for (int i = 0; i < zl; i++) {
 
1216
        uint xu = getOne(negx, xd, i, ref seenNonZeroX);
 
1217
        uint yu = getOne(negy, yd, i, ref seenNonZeroY);
 
1218
        zd[i] = xu & yu;
 
1219
      }
 
1220
 
 
1221
      if (negx && negy) {
 
1222
 
 
1223
        return new BigInteger(-1, makeTwosComplement(zd));
 
1224
      } else if (negx || negy) {
 
1225
        return new BigInteger(+1, zd);
 
1226
      } else {
 
1227
        return new BigInteger(+1, zd);
 
1228
      }
 
1229
    }
 
1230
 
 
1231
    public static BigInteger BitwiseOr(BigInteger x, BigInteger y) {
 
1232
      return x | y;
 
1233
    }
 
1234
 
 
1235
    public static BigInteger operator |(BigInteger x, BigInteger y) {
 
1236
      if (object.ReferenceEquals(x, null)) {
 
1237
        throw new ArgumentNullException("x");
 
1238
      }
 
1239
      if (object.ReferenceEquals(y, null)) {
 
1240
        throw new ArgumentNullException("y");
 
1241
      }
 
1242
      int xl = x.Length, yl = y.Length;
 
1243
      uint[] xd = x.data, yd = y.data;
 
1244
 
 
1245
      int zl = System.Math.Max(xl, yl);
 
1246
      uint[] zd = new uint[zl];
 
1247
 
 
1248
      bool negx = x.sign == -1, negy = y.sign == -1;
 
1249
      bool seenNonZeroX = false, seenNonZeroY = false;
 
1250
      for (int i = 0; i < zl; i++) {
 
1251
        uint xu = getOne(negx, xd, i, ref seenNonZeroX);
 
1252
        uint yu = getOne(negy, yd, i, ref seenNonZeroY);
 
1253
        zd[i] = xu | yu;
 
1254
      }
 
1255
 
 
1256
      if (negx && negy) {
 
1257
        return new BigInteger(-1, makeTwosComplement(zd));
 
1258
      } else if (negx || negy) {
 
1259
        return new BigInteger(-1, makeTwosComplement(zd));
 
1260
      } else {
 
1261
        return new BigInteger(+1, zd);
 
1262
      }
 
1263
    }
 
1264
 
 
1265
    public static BigInteger Xor(BigInteger x, BigInteger y) {
 
1266
      return x ^ y;
 
1267
    }
 
1268
 
 
1269
    public static BigInteger operator ^(BigInteger x, BigInteger y) {
 
1270
      if (object.ReferenceEquals(x, null)) {
 
1271
        throw new ArgumentNullException("x");
 
1272
      }
 
1273
      if (object.ReferenceEquals(y, null)) {
 
1274
        throw new ArgumentNullException("y");
 
1275
      }
 
1276
      int xl = x.Length, yl = y.Length;
 
1277
      uint[] xd = x.data, yd = y.data;
 
1278
 
 
1279
      int zl = System.Math.Max(xl, yl);
 
1280
      uint[] zd = new uint[zl];
 
1281
 
 
1282
      bool negx = x.sign == -1, negy = y.sign == -1;
 
1283
      bool seenNonZeroX = false, seenNonZeroY = false;
 
1284
      for (int i = 0; i < zl; i++) {
 
1285
        uint xu = getOne(negx, xd, i, ref seenNonZeroX);
 
1286
        uint yu = getOne(negy, yd, i, ref seenNonZeroY);
 
1287
        zd[i] = xu ^ yu;
 
1288
      }
 
1289
 
 
1290
      if (negx && negy) {
 
1291
        return new BigInteger(+1, zd);
 
1292
      } else if (negx || negy) {
 
1293
        return new BigInteger(-1, makeTwosComplement(zd));
 
1294
      } else {
 
1295
        return new BigInteger(+1, zd);
 
1296
      }
 
1297
    }
 
1298
 
 
1299
    public static BigInteger LeftShift(BigInteger x, int shift) {
 
1300
      return x << shift;
 
1301
    }
 
1302
 
 
1303
    public static BigInteger operator <<(BigInteger x, int shift) {
 
1304
      if (object.ReferenceEquals(x, null)) {
 
1305
        throw new ArgumentNullException("x");
 
1306
      }
 
1307
      if (shift == 0) return x;
 
1308
      else if (shift < 0) return x >> -shift;
 
1309
 
 
1310
      int digitShift = shift / BitsPerDigit;
 
1311
      int smallShift = shift - (digitShift * BitsPerDigit);
 
1312
 
 
1313
      int xl = x.Length;
 
1314
      uint[] xd = x.data;
 
1315
      int zl = xl + digitShift + 1;
 
1316
      uint[] zd = new uint[zl];
 
1317
 
 
1318
      if (smallShift == 0) {
 
1319
        for (int i = 0; i < xl; i++) {
 
1320
          zd[i + digitShift] = xd[i];
 
1321
        }
 
1322
      } else {
 
1323
        int carryShift = BitsPerDigit - smallShift;
 
1324
        uint carry = 0;
 
1325
        int i;
 
1326
        for (i = 0; i < xl; i++) {
 
1327
          uint rot = xd[i];
 
1328
          zd[i + digitShift] = rot << smallShift | carry;
 
1329
          carry = rot >> carryShift;
 
1330
        }
 
1331
        zd[i + digitShift] = carry;
 
1332
      }
 
1333
      return new BigInteger(x.sign, zd);
 
1334
    }
 
1335
 
 
1336
    public static BigInteger RightShift(BigInteger x, int shift) {
 
1337
      return x >> shift;
 
1338
    }
 
1339
 
 
1340
    public static BigInteger operator >>(BigInteger x, int shift) {
 
1341
      if (object.ReferenceEquals(x, null)) {
 
1342
        throw new ArgumentNullException("x");
 
1343
      }
 
1344
      if (shift == 0) return x;
 
1345
      else if (shift < 0) return x << -shift;
 
1346
 
 
1347
      int digitShift = shift / BitsPerDigit;
 
1348
      int smallShift = shift - (digitShift * BitsPerDigit);
 
1349
 
 
1350
      int xl = x.Length;
 
1351
      uint[] xd = x.data;
 
1352
      int zl = xl - digitShift;
 
1353
      if (zl < 0) zl = 0;
 
1354
      uint[] zd = new uint[zl];
 
1355
 
 
1356
      if (smallShift == 0) {
 
1357
        for (int i = xl - 1; i >= digitShift; i--) {
 
1358
          zd[i - digitShift] = xd[i];
 
1359
        }
 
1360
      } else {
 
1361
        int carryShift = BitsPerDigit - smallShift;
 
1362
        uint carry = 0;
 
1363
        for (int i = xl - 1; i >= digitShift; i--) {
 
1364
          uint rot = xd[i];
 
1365
          zd[i - digitShift] = rot >> smallShift | carry;
 
1366
          carry = rot << carryShift;
 
1367
        }
 
1368
      }
 
1369
      return new BigInteger(x.sign, zd);
 
1370
    }
 
1371
 
 
1372
    public static BigInteger Negate(BigInteger x) {
 
1373
      return -x;
 
1374
    }
 
1375
 
 
1376
    public static BigInteger operator -(BigInteger x) {
 
1377
      if (object.ReferenceEquals(x, null)) {
 
1378
        throw new ArgumentNullException("x");
 
1379
      }
 
1380
      return new BigInteger(-x.sign, x.data);
 
1381
    }
 
1382
 
 
1383
    public BigInteger OnesComplement() {
 
1384
      return ~this;
 
1385
    }
 
1386
 
 
1387
    public static BigInteger operator ~(BigInteger x) {
 
1388
      if (object.ReferenceEquals(x, null)) {
 
1389
        throw new ArgumentNullException("x");
 
1390
      }
 
1391
      return -(x + One);
 
1392
    }
 
1393
 
 
1394
    public BigInteger Abs() {
 
1395
      if (this.sign == -1) return -this;
 
1396
      else return this;
 
1397
    }
 
1398
 
 
1399
    public BigInteger Power(int exp) {
 
1400
      if (exp == 0) return One;
 
1401
      if (exp < 0) {
 
1402
        throw new ArgumentOutOfRangeException(MathResources.NonNegativePower);
 
1403
      }
 
1404
      BigInteger factor = this;
 
1405
      BigInteger result = One;
 
1406
      while (exp != 0) {
 
1407
        if ((exp & 1) != 0) result = result * factor;
 
1408
        if (exp == 1) break;  // avoid costly factor.square()
 
1409
        factor = factor.Square();
 
1410
        exp >>= 1;
 
1411
      }
 
1412
      return result;
 
1413
    }
 
1414
 
 
1415
    public BigInteger ModPow(int power, BigInteger mod) {
 
1416
      if (object.ReferenceEquals(mod, null)) {
 
1417
        throw new ArgumentNullException("mod");
 
1418
      }
 
1419
 
 
1420
      if (power < 0) {
 
1421
        throw new ArgumentOutOfRangeException(MathResources.NonNegativePower);
 
1422
      }
 
1423
      BigInteger factor = this;
 
1424
      BigInteger result = One % mod; // Handle special case of power=0, mod=1
 
1425
      while (power != 0) {
 
1426
        if ((power & 1) != 0) {
 
1427
          result = result * factor;
 
1428
          result = result % mod;
 
1429
        }
 
1430
        if (power == 1) break;  // avoid costly factor.Square()
 
1431
        factor = factor.Square();
 
1432
        factor = factor % mod;
 
1433
        power >>= 1;
 
1434
      }
 
1435
      return result;
 
1436
    }
 
1437
 
 
1438
    public BigInteger ModPow(BigInteger power, BigInteger mod) {
 
1439
      if (object.ReferenceEquals(power, null)) {
 
1440
        throw new ArgumentNullException("power");
 
1441
      }
 
1442
      if (object.ReferenceEquals(mod, null)) {
 
1443
        throw new ArgumentNullException("mod");
 
1444
      }
 
1445
 
 
1446
      if (power < 0) {
 
1447
        throw new ArgumentOutOfRangeException(MathResources.NonNegativePower);
 
1448
      }
 
1449
 
 
1450
      BigInteger factor = this;
 
1451
      BigInteger result = One % mod;
 
1452
      while (power != Zero) {
 
1453
        if (power.IsOdd()) {
 
1454
          result = result * factor;
 
1455
          result = result % mod;
 
1456
        }
 
1457
        if (power == One) break;  // avoid costly factor.Square()
 
1458
        factor = factor.Square();
 
1459
        factor = factor % mod;
 
1460
        power >>= 1;
 
1461
      }
 
1462
      return result;
 
1463
    }
 
1464
 
 
1465
    public BigInteger Square() {
 
1466
      return this * this;
 
1467
    }
 
1468
 
 
1469
    public override string ToString() {
 
1470
      return ToString(10);
 
1471
    }
 
1472
 
 
1473
    // generated by scripts/radix_generator.py
 
1474
    //RI: made fields read-only to comply with security requirements for SQL Server-imported assemblies
 
1475
    private static readonly uint[] maxCharsPerDigit = { 0, 0, 31, 20, 15, 13, 12, 11, 10, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6 };
 
1476
    private static readonly uint[] groupRadixValues = { 0, 0, 2147483648, 3486784401, 1073741824, 1220703125, 2176782336, 1977326743, 1073741824, 3486784401, 1000000000, 2357947691, 429981696, 815730721, 1475789056, 2562890625, 268435456, 410338673, 612220032, 893871739, 1280000000, 1801088541, 2494357888, 3404825447, 191102976, 244140625, 308915776, 387420489, 481890304, 594823321, 729000000, 887503681, 1073741824, 1291467969, 1544804416, 1838265625, 2176782336 };
 
1477
 
 
1478
 
 
1479
    [CLSCompliant(false)]
 
1480
    public string ToString(uint radix) {
 
1481
      if (radix < 2) {
 
1482
        throw new ArgumentOutOfRangeException("radix", radix, MathResources.RadixLessThan2);
 
1483
      }
 
1484
      if (radix > 36) {
 
1485
        throw new ArgumentOutOfRangeException("radix", radix, MathResources.RadixGreaterThan36);
 
1486
      }
 
1487
 
 
1488
      int len = Length;
 
1489
      if (len == 0) return "0";
 
1490
 
 
1491
      List<uint> digitGroups = new List<uint>();
 
1492
 
 
1493
      uint[] d = copy(data);
 
1494
      int dl = Length;
 
1495
 
 
1496
      uint groupRadix = groupRadixValues[radix];
 
1497
      while (dl > 0) {
 
1498
        uint rem = div(d, ref dl, groupRadix);
 
1499
        digitGroups.Add(rem);
 
1500
      }
 
1501
 
 
1502
      StringBuilder ret = new StringBuilder();
 
1503
      if (sign == -1) ret.Append("-");
 
1504
      int digitIndex = digitGroups.Count - 1;
 
1505
 
 
1506
      char[] tmpDigits = new char[maxCharsPerDigit[radix]];
 
1507
 
 
1508
      AppendRadix((uint)digitGroups[digitIndex--], radix, tmpDigits, ret, false);
 
1509
      while (digitIndex >= 0) {
 
1510
        AppendRadix((uint)digitGroups[digitIndex--], radix, tmpDigits, ret, true);
 
1511
      }
 
1512
      return ret.ToString();
 
1513
    }
 
1514
 
 
1515
    private static void AppendRadix(uint rem, uint radix, char[] tmp, StringBuilder buf, bool leadingZeros) {
 
1516
      const string symbols = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 
1517
 
 
1518
      int digits = tmp.Length;
 
1519
      int i = digits;
 
1520
      while (i > 0 && (leadingZeros || rem != 0)) {
 
1521
        uint digit = rem % radix;
 
1522
        rem /= radix;
 
1523
        tmp[--i] = symbols[(int)digit];
 
1524
      }
 
1525
      if (leadingZeros) buf.Append(tmp);
 
1526
      else buf.Append(tmp, i, digits - i);
 
1527
    }
 
1528
 
 
1529
    public override int GetHashCode() {
 
1530
      if (data.Length == 0) return 0;
 
1531
      // HashCode must be same as int for values in the range of a single int
 
1532
      if (IsNegative())
 
1533
        return -(int)data[0];
 
1534
 
 
1535
      return (int)data[0];
 
1536
    }
 
1537
 
 
1538
    public override bool Equals(object obj) {
 
1539
      BigInteger o = obj as BigInteger;
 
1540
      if (object.ReferenceEquals(o, null)) return false;
 
1541
      return this == o;
 
1542
    }
 
1543
 
 
1544
    public bool IsNegative() {
 
1545
      return sign < 0;
 
1546
    }
 
1547
 
 
1548
    public bool IsZero() {
 
1549
      return sign == 0;
 
1550
    }
 
1551
 
 
1552
    public bool IsPositive() {
 
1553
      return sign > 0;
 
1554
    }
 
1555
 
 
1556
    private bool IsOdd() {
 
1557
      // must have the lowest-order bit set to 1
 
1558
      return (data != null && data.Length > 0 && ((data[0] & 1) != 0));
 
1559
    }
 
1560
 
 
1561
    #region IComparable Members
 
1562
 
 
1563
    public int CompareTo(object obj) {
 
1564
      if (obj == null) {
 
1565
        return 1;
 
1566
      }
 
1567
      BigInteger o = obj as BigInteger;
 
1568
      if (object.ReferenceEquals(o, null)) {
 
1569
        throw new ArgumentException(MathResources.ExpectedInteger);
 
1570
      }
 
1571
      return Compare(this, o);
 
1572
    }
 
1573
 
 
1574
    #endregion
 
1575
 
 
1576
    #region IConvertible Members
 
1577
 
 
1578
    public TypeCode GetTypeCode() {
 
1579
      return TypeCode.Object;
 
1580
    }
 
1581
 
 
1582
    public bool ToBoolean(IFormatProvider provider) {
 
1583
      return this != Zero;
 
1584
    }
 
1585
 
 
1586
    public byte ToByte(IFormatProvider provider) {
 
1587
      uint ret;
 
1588
      if (AsUInt32(out ret) && (ret & ~0xFF) == 0) {
 
1589
        return (byte)ret;
 
1590
      }
 
1591
      throw new OverflowException(MathResources.BigIntWontFitByte);
 
1592
    }
 
1593
 
 
1594
    /// <summary>
 
1595
    /// Return the value of this BigInteger as a little-endian twos-complement
 
1596
    /// byte array, using the fewest number of bytes possible. If the value is zero,
 
1597
    /// return an array of one byte whose element is 0x00.
 
1598
    /// </summary>
 
1599
    public byte[] ToByteArray() {
 
1600
      // We could probably make this more efficient by eliminating one of the passes.
 
1601
      // The current code does one pass for uint array -> byte array conversion,
 
1602
      // and then a another pass to remove unneeded bytes at the top of the array.
 
1603
      if (0 == sign) return new byte[] { 0 };
 
1604
 
 
1605
      uint[] dwords;
 
1606
      byte highByte;
 
1607
 
 
1608
      if (-1 == sign) {
 
1609
        dwords = (uint[])this.data.Clone();
 
1610
        makeTwosComplement(dwords);
 
1611
        highByte = 0xff;
 
1612
      } else {
 
1613
        dwords = this.data;
 
1614
        highByte = 0x00;
 
1615
      }
 
1616
 
 
1617
      byte[] bytes = new byte[4 * dwords.Length];
 
1618
      int curByte = 0;
 
1619
      uint dword;
 
1620
      for (int i = 0; i < dwords.Length; i++) {
 
1621
        dword = dwords[i];
 
1622
        for (int j = 0; j < 4; j++) {
 
1623
          bytes[curByte++] = (byte)(dword & 0xff);
 
1624
          dword >>= 8;
 
1625
        }
 
1626
      }
 
1627
 
 
1628
      // find highest significant byte
 
1629
      int msb;
 
1630
      for (msb = bytes.Length - 1; msb > 0; msb--) {
 
1631
        if (bytes[msb] != highByte) break;
 
1632
      }
 
1633
      // ensure high bit is 0 if positive, 1 if negative
 
1634
      bool needExtraByte = (bytes[msb] & 0x80) != (highByte & 0x80);
 
1635
 
 
1636
      byte[] trimmedBytes = new byte[msb + 1 + (needExtraByte ? 1 : 0)];
 
1637
      Array.Copy(bytes, trimmedBytes, msb + 1);
 
1638
 
 
1639
      if (needExtraByte) trimmedBytes[trimmedBytes.Length - 1] = highByte;
 
1640
 
 
1641
      return trimmedBytes;
 
1642
    }
 
1643
 
 
1644
    public char ToChar(IFormatProvider provider) {
 
1645
      int ret;
 
1646
      if (AsInt32(out ret) && (ret <= Char.MaxValue) && (ret >= Char.MinValue)) {
 
1647
        return (char)ret;
 
1648
      }
 
1649
      throw new OverflowException(MathResources.BigIntWontFitChar);
 
1650
    }
 
1651
 
 
1652
    public DateTime ToDateTime(IFormatProvider provider) {
 
1653
      throw new NotImplementedException();
 
1654
    }
 
1655
 
 
1656
    public decimal ToDecimal(IFormatProvider provider) {
 
1657
      decimal ret;
 
1658
      if (AsDecimal(out ret)) return ret;
 
1659
      throw new OverflowException(MathResources.BigIntWontFitDecimal);
 
1660
    }
 
1661
 
 
1662
    public double ToDouble(IFormatProvider provider) {
 
1663
      return ToFloat64();
 
1664
    }
 
1665
 
 
1666
    public short ToInt16(IFormatProvider provider) {
 
1667
      int ret;
 
1668
      if (AsInt32(out ret) && (ret <= short.MaxValue) && (ret >= short.MinValue)) {
 
1669
        return (short)ret;
 
1670
      }
 
1671
      throw new OverflowException(MathResources.BigIntWontFitShort);
 
1672
    }
 
1673
 
 
1674
    public int ToInt32(IFormatProvider provider) {
 
1675
      int ret;
 
1676
      if (AsInt32(out ret)) {
 
1677
        return ret;
 
1678
      }
 
1679
      throw new OverflowException(MathResources.BigIntWontFitInt);
 
1680
    }
 
1681
 
 
1682
    public long ToInt64(IFormatProvider provider) {
 
1683
      long ret;
 
1684
      if (AsInt64(out ret)) {
 
1685
        return ret;
 
1686
      }
 
1687
      throw new OverflowException(MathResources.BigIntWontFitLong);
 
1688
    }
 
1689
 
 
1690
    [CLSCompliant(false)]
 
1691
    public sbyte ToSByte(IFormatProvider provider) {
 
1692
      int ret;
 
1693
      if (AsInt32(out ret) && (ret <= sbyte.MaxValue) && (ret >= sbyte.MinValue)) {
 
1694
        return (sbyte)ret;
 
1695
      }
 
1696
      throw new OverflowException(MathResources.BigIntWontFitSByte);
 
1697
    }
 
1698
 
 
1699
    public float ToSingle(IFormatProvider provider) {
 
1700
      return checked((float)ToDouble(provider));
 
1701
    }
 
1702
 
 
1703
    public string ToString(IFormatProvider provider) {
 
1704
      return ToString();
 
1705
    }
 
1706
 
 
1707
    public object ToType(Type conversionType, IFormatProvider provider) {
 
1708
      if (conversionType == typeof(BigInteger)) {
 
1709
        return this;
 
1710
      }
 
1711
      throw new NotImplementedException();
 
1712
    }
 
1713
 
 
1714
    [CLSCompliant(false)]
 
1715
    public ushort ToUInt16(IFormatProvider provider) {
 
1716
      uint ret;
 
1717
      if (AsUInt32(out ret) && ret <= ushort.MaxValue) {
 
1718
        return (ushort)ret;
 
1719
      }
 
1720
      throw new OverflowException(MathResources.BigIntWontFitUShort);
 
1721
    }
 
1722
 
 
1723
    [CLSCompliant(false)]
 
1724
    public uint ToUInt32(IFormatProvider provider) {
 
1725
      uint ret;
 
1726
      if (AsUInt32(out ret)) {
 
1727
        return ret;
 
1728
      }
 
1729
      throw new OverflowException(MathResources.BigIntWontFitUInt);
 
1730
    }
 
1731
 
 
1732
    [CLSCompliant(false)]
 
1733
    public ulong ToUInt64(IFormatProvider provider) {
 
1734
      ulong ret;
 
1735
      if (AsUInt64(out ret)) {
 
1736
        return ret;
 
1737
      }
 
1738
      throw new OverflowException(MathResources.BigIntWontFitULong);
 
1739
    }
 
1740
 
 
1741
    #endregion
 
1742
 
 
1743
    #region IFormattable Members
 
1744
 
 
1745
    string IFormattable.ToString(string format, IFormatProvider formatProvider) {
 
1746
      if (format == null) return this.ToString();
 
1747
 
 
1748
      switch (format[0]) {
 
1749
        case 'd':
 
1750
        case 'D':
 
1751
          if (format.Length > 1) {
 
1752
            int precision = Convert.ToInt32(format.Substring(1), CultureInfo.InvariantCulture.NumberFormat);
 
1753
            string baseStr = ToString(10);
 
1754
            if (baseStr.Length < precision) {
 
1755
              string additional = new String('0', precision - baseStr.Length);
 
1756
              if (baseStr[0] != '-') {
 
1757
                return additional + baseStr;
 
1758
              } else {
 
1759
                return "-" + additional + baseStr.Substring(1);
 
1760
              }
 
1761
            }
 
1762
            return baseStr;
 
1763
          }
 
1764
          return ToString(10);
 
1765
        case 'x':
 
1766
        case 'X':
 
1767
          StringBuilder res = new StringBuilder(ToString(16));
 
1768
          if (format[0] == 'x') {
 
1769
            for (int i = 0; i < res.Length; i++) {
 
1770
              if (res[i] >= 'A' && res[i] <= 'F') {
 
1771
                res[i] = Char.ToLowerInvariant(res[i]);
 
1772
              }
 
1773
            }
 
1774
          }
 
1775
 
 
1776
          if (format.Length > 1) {
 
1777
            int precision = Convert.ToInt32(format.Substring(1), CultureInfo.InvariantCulture.NumberFormat);
 
1778
            if (res.Length < precision) {
 
1779
              string additional = new String('0', precision - res.Length);
 
1780
              if (res[0] != '-') {
 
1781
                res.Insert(0, additional);
 
1782
              } else {
 
1783
                res.Insert(1, additional);
 
1784
              }
 
1785
            }
 
1786
          }
 
1787
 
 
1788
          return res.ToString();
 
1789
        default:
 
1790
          throw new NotImplementedException(MathResources.FormatNotImplemented);
 
1791
      }
 
1792
    }
 
1793
 
 
1794
    #endregion
 
1795
 
 
1796
 
 
1797
  }//class
 
1798
}//namespace