OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libjava/] [classpath/] [java/] [math/] [BigInteger.java] - Blame information for rev 791

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 771 jeremybenn
/* java.math.BigInteger -- Arbitary precision integers
2
   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2005, 2006, 2007  Free Software Foundation, Inc.
3
 
4
This file is part of GNU Classpath.
5
 
6
GNU Classpath is free software; you can redistribute it and/or modify
7
it under the terms of the GNU General Public License as published by
8
the Free Software Foundation; either version 2, or (at your option)
9
any later version.
10
 
11
GNU Classpath is distributed in the hope that it will be useful, but
12
WITHOUT ANY WARRANTY; without even the implied warranty of
13
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14
General Public License for more details.
15
 
16
You should have received a copy of the GNU General Public License
17
along with GNU Classpath; see the file COPYING.  If not, write to the
18
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19
02110-1301 USA.
20
 
21
Linking this library statically or dynamically with other modules is
22
making a combined work based on this library.  Thus, the terms and
23
conditions of the GNU General Public License cover the whole
24
combination.
25
 
26
As a special exception, the copyright holders of this library give you
27
permission to link this library with independent modules to produce an
28
executable, regardless of the license terms of these independent
29
modules, and to copy and distribute the resulting executable under
30
terms of your choice, provided that you also meet, for each linked
31
independent module, the terms and conditions of the license of that
32
module.  An independent module is a module which is not derived from
33
or based on this library.  If you modify this library, you may extend
34
this exception to your version of the library, but you are not
35
obligated to do so.  If you do not wish to do so, delete this
36
exception statement from your version. */
37
 
38
 
39
package java.math;
40
 
41
import gnu.classpath.Configuration;
42
 
43
import gnu.java.lang.CPStringBuilder;
44
import gnu.java.math.GMP;
45
import gnu.java.math.MPN;
46
 
47
import java.io.IOException;
48
import java.io.ObjectInputStream;
49
import java.io.ObjectOutputStream;
50
import java.util.Random;
51
import java.util.logging.Logger;
52
 
53
/**
54
 * Written using on-line Java Platform 1.2 API Specification, as well
55
 * as "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998) and
56
 * "Applied Cryptography, Second Edition" by Bruce Schneier (Wiley, 1996).
57
 *
58
 * Based primarily on IntNum.java BitOps.java by Per Bothner (per@bothner.com)
59
 * (found in Kawa 1.6.62).
60
 *
61
 * @author Warren Levy (warrenl@cygnus.com)
62
 * @date December 20, 1999.
63
 * @status believed complete and correct.
64
 */
65
public class BigInteger extends Number implements Comparable<BigInteger>
66
{
67
  private static final Logger log = Logger.getLogger(BigInteger.class.getName());
68
 
69
  /** All integers are stored in 2's-complement form.
70
   * If words == null, the ival is the value of this BigInteger.
71
   * Otherwise, the first ival elements of words make the value
72
   * of this BigInteger, stored in little-endian order, 2's-complement form. */
73
  private transient int ival;
74
  private transient int[] words;
75
 
76
  // Serialization fields.
77
  // the first three, although not used in the code, are present for
78
  // compatibility with older RI versions of this class. DO NOT REMOVE.
79
  private int bitCount = -1;
80
  private int bitLength = -1;
81
  private int lowestSetBit = -2;
82
  private byte[] magnitude;
83
  private int signum;
84
  private static final long serialVersionUID = -8287574255936472291L;
85
 
86
 
87
  /** We pre-allocate integers in the range minFixNum..maxFixNum.
88
   * Note that we must at least preallocate 0, 1, and 10.  */
89
  private static final int minFixNum = -100;
90
  private static final int maxFixNum = 1024;
91
  private static final int numFixNum = maxFixNum-minFixNum+1;
92
  private static final BigInteger[] smallFixNums;
93
 
94
  /** The alter-ego GMP instance for this. */
95
  private transient GMP mpz;
96
 
97
  private static final boolean USING_NATIVE = Configuration.WANT_NATIVE_BIG_INTEGER
98
                                              && initializeLibrary();
99
 
100
  static
101
  {
102
    if (USING_NATIVE)
103
      {
104
        smallFixNums = null;
105
        ZERO = valueOf(0L);
106
        ONE = valueOf(1L);
107
        TEN = valueOf(10L);
108
      }
109
    else
110
      {
111
        smallFixNums = new BigInteger[numFixNum];
112
        for (int i = numFixNum;  --i >= 0; )
113
          smallFixNums[i] = new BigInteger(i + minFixNum);
114
 
115
        ZERO = smallFixNums[-minFixNum];
116
        ONE = smallFixNums[1 - minFixNum];
117
        TEN = smallFixNums[10 - minFixNum];
118
      }
119
  }
120
 
121
  /**
122
   * The constant zero as a BigInteger.
123
   * @since 1.2
124
   */
125
  public static final BigInteger ZERO;
126
 
127
  /**
128
   * The constant one as a BigInteger.
129
   * @since 1.2
130
   */
131
  public static final BigInteger ONE;
132
 
133
  /**
134
   * The constant ten as a BigInteger.
135
   * @since 1.5
136
   */
137
  public static final BigInteger TEN;
138
 
139
  /* Rounding modes: */
140
  private static final int FLOOR = 1;
141
  private static final int CEILING = 2;
142
  private static final int TRUNCATE = 3;
143
  private static final int ROUND = 4;
144
 
145
  /** When checking the probability of primes, it is most efficient to
146
   * first check the factoring of small primes, so we'll use this array.
147
   */
148
  private static final int[] primes =
149
    {   2,   3,   5,   7,  11,  13,  17,  19,  23,  29,  31,  37,  41,  43,
150
       47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97, 101, 103, 107,
151
      109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
152
      191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 };
153
 
154
  /** HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Table 4.4. */
155
  private static final int[] k =
156
      {100,150,200,250,300,350,400,500,600,800,1250, Integer.MAX_VALUE};
157
  private static final int[] t =
158
      { 27, 18, 15, 12,  9,  8,  7,  6,  5,  4,   3, 2};
159
 
160
  private BigInteger()
161
  {
162
    super();
163
 
164
    if (USING_NATIVE)
165
      mpz = new GMP();
166
  }
167
 
168
  /* Create a new (non-shared) BigInteger, and initialize to an int. */
169
  private BigInteger(int value)
170
  {
171
    super();
172
 
173
    ival = value;
174
  }
175
 
176
  public BigInteger(String s, int radix)
177
  {
178
    this();
179
 
180
    int len = s.length();
181
    int i, digit;
182
    boolean negative;
183
    byte[] bytes;
184
    char ch = s.charAt(0);
185
    if (ch == '-')
186
      {
187
        negative = true;
188
        i = 1;
189
        bytes = new byte[len - 1];
190
      }
191
    else
192
      {
193
        negative = false;
194
        i = 0;
195
        bytes = new byte[len];
196
      }
197
    int byte_len = 0;
198
    for ( ; i < len;  i++)
199
      {
200
        ch = s.charAt(i);
201
        digit = Character.digit(ch, radix);
202
        if (digit < 0)
203
          throw new NumberFormatException("Invalid character at position #" + i);
204
        bytes[byte_len++] = (byte) digit;
205
      }
206
 
207
    if (USING_NATIVE)
208
      {
209
        bytes = null;
210
        if (mpz.fromString(s, radix) != 0)
211
          throw new NumberFormatException("String \"" + s
212
                                          + "\" is NOT a valid number in base "
213
                                          + radix);
214
      }
215
    else
216
      {
217
        BigInteger result;
218
        // Testing (len < MPN.chars_per_word(radix)) would be more accurate,
219
        // but slightly more expensive, for little practical gain.
220
        if (len <= 15 && radix <= 16)
221
          result = valueOf(Long.parseLong(s, radix));
222
        else
223
          result = valueOf(bytes, byte_len, negative, radix);
224
 
225
        this.ival = result.ival;
226
        this.words = result.words;
227
      }
228
  }
229
 
230
  public BigInteger(String val)
231
  {
232
    this(val, 10);
233
  }
234
 
235
  /* Create a new (non-shared) BigInteger, and initialize from a byte array. */
236
  public BigInteger(byte[] val)
237
  {
238
    this();
239
 
240
    if (val == null || val.length < 1)
241
      throw new NumberFormatException();
242
 
243
    if (USING_NATIVE)
244
      mpz.fromByteArray(val);
245
    else
246
      {
247
        words = byteArrayToIntArray(val, val[0] < 0 ? -1 : 0);
248
        BigInteger result = make(words, words.length);
249
        this.ival = result.ival;
250
        this.words = result.words;
251
      }
252
  }
253
 
254
  public BigInteger(int signum, byte[] magnitude)
255
  {
256
    this();
257
 
258
    if (magnitude == null || signum > 1 || signum < -1)
259
      throw new NumberFormatException();
260
 
261
    if (signum == 0)
262
      {
263
        int i;
264
        for (i = magnitude.length - 1; i >= 0 && magnitude[i] == 0; --i)
265
          ;
266
        if (i >= 0)
267
          throw new NumberFormatException();
268
        return;
269
      }
270
 
271
    if (USING_NATIVE)
272
      mpz.fromSignedMagnitude(magnitude, signum == -1);
273
    else
274
      {
275
        // Magnitude is always positive, so don't ever pass a sign of -1.
276
        words = byteArrayToIntArray(magnitude, 0);
277
        BigInteger result = make(words, words.length);
278
        this.ival = result.ival;
279
        this.words = result.words;
280
 
281
        if (signum < 0)
282
          setNegative();
283
      }
284
  }
285
 
286
  public BigInteger(int numBits, Random rnd)
287
  {
288
    this();
289
 
290
    if (numBits < 0)
291
      throw new IllegalArgumentException();
292
 
293
    init(numBits, rnd);
294
  }
295
 
296
  private void init(int numBits, Random rnd)
297
  {
298
    if (USING_NATIVE)
299
      {
300
        int length = (numBits + 7) / 8;
301
        byte[] magnitude = new byte[length];
302
        rnd.nextBytes(magnitude);
303
        int discardedBitCount = numBits % 8;
304
        if (discardedBitCount != 0)
305
          {
306
            discardedBitCount = 8 - discardedBitCount;
307
            magnitude[0] = (byte)((magnitude[0] & 0xFF) >>> discardedBitCount);
308
          }
309
        mpz.fromSignedMagnitude(magnitude, false);
310
        magnitude = null;
311
        return;
312
      }
313
 
314
    int highbits = numBits & 31;
315
    // minimum number of bytes to store the above number of bits
316
    int highBitByteCount = (highbits + 7) / 8;
317
    // number of bits to discard from the last byte
318
    int discardedBitCount = highbits % 8;
319
    if (discardedBitCount != 0)
320
      discardedBitCount = 8 - discardedBitCount;
321
    byte[] highBitBytes = new byte[highBitByteCount];
322
    if (highbits > 0)
323
      {
324
        rnd.nextBytes(highBitBytes);
325
        highbits = (highBitBytes[highBitByteCount - 1] & 0xFF) >>> discardedBitCount;
326
        for (int i = highBitByteCount - 2; i >= 0; i--)
327
          highbits = (highbits << 8) | (highBitBytes[i] & 0xFF);
328
      }
329
    int nwords = numBits / 32;
330
 
331
    while (highbits == 0 && nwords > 0)
332
      {
333
        highbits = rnd.nextInt();
334
        --nwords;
335
      }
336
    if (nwords == 0 && highbits >= 0)
337
      {
338
        ival = highbits;
339
      }
340
    else
341
      {
342
        ival = highbits < 0 ? nwords + 2 : nwords + 1;
343
        words = new int[ival];
344
        words[nwords] = highbits;
345
        while (--nwords >= 0)
346
          words[nwords] = rnd.nextInt();
347
      }
348
  }
349
 
350
  public BigInteger(int bitLength, int certainty, Random rnd)
351
  {
352
    this();
353
 
354
    BigInteger result = new BigInteger();
355
    while (true)
356
      {
357
        result.init(bitLength, rnd);
358
        result = result.setBit(bitLength - 1);
359
        if (result.isProbablePrime(certainty))
360
          break;
361
      }
362
 
363
    if (USING_NATIVE)
364
      mpz.fromBI(result.mpz);
365
    else
366
      {
367
        this.ival = result.ival;
368
        this.words = result.words;
369
      }
370
  }
371
 
372
  /**
373
   *  Return a BigInteger that is bitLength bits long with a
374
   *  probability < 2^-100 of being composite.
375
   *
376
   *  @param bitLength length in bits of resulting number
377
   *  @param rnd random number generator to use
378
   *  @throws ArithmeticException if bitLength < 2
379
   *  @since 1.4
380
   */
381
  public static BigInteger probablePrime(int bitLength, Random rnd)
382
  {
383
    if (bitLength < 2)
384
      throw new ArithmeticException();
385
 
386
    return new BigInteger(bitLength, 100, rnd);
387
  }
388
 
389
  /** Return a (possibly-shared) BigInteger with a given long value. */
390
  public static BigInteger valueOf(long val)
391
  {
392
    if (USING_NATIVE)
393
      {
394
        BigInteger result = new BigInteger();
395
        result.mpz.fromLong(val);
396
        return result;
397
      }
398
 
399
    if (val >= minFixNum && val <= maxFixNum)
400
      return smallFixNums[(int) val - minFixNum];
401
    int i = (int) val;
402
    if ((long) i == val)
403
      return new BigInteger(i);
404
    BigInteger result = alloc(2);
405
    result.ival = 2;
406
    result.words[0] = i;
407
    result.words[1] = (int)(val >> 32);
408
    return result;
409
  }
410
 
411
  /**
412
   * @return <code>true</code> if the GMP-based native implementation library
413
   *         was successfully loaded. Returns <code>false</code> otherwise.
414
   */
415
  private static boolean initializeLibrary()
416
  {
417
    boolean result;
418
    try
419
    {
420
      System.loadLibrary("javamath");
421
      GMP.natInitializeLibrary();
422
      result = true;
423
    }
424
    catch (Throwable x)
425
    {
426
      result = false;
427
      if (Configuration.DEBUG)
428
        {
429
          log.info("Unable to use native BigInteger: " + x);
430
          log.info("Will use a pure Java implementation instead");
431
        }
432
    }
433
    return result;
434
  }
435
 
436
  /** Make a canonicalized BigInteger from an array of words.
437
   * The array may be reused (without copying). */
438
  private static BigInteger make(int[] words, int len)
439
  {
440
    if (words == null)
441
      return valueOf(len);
442
    len = BigInteger.wordsNeeded(words, len);
443
    if (len <= 1)
444
      return len == 0 ? ZERO : valueOf(words[0]);
445
    BigInteger num = new BigInteger();
446
    num.words = words;
447
    num.ival = len;
448
    return num;
449
  }
450
 
451
  /** Convert a big-endian byte array to a little-endian array of words. */
452
  private static int[] byteArrayToIntArray(byte[] bytes, int sign)
453
  {
454
    // Determine number of words needed.
455
    int[] words = new int[bytes.length/4 + 1];
456
    int nwords = words.length;
457
 
458
    // Create a int out of modulo 4 high order bytes.
459
    int bptr = 0;
460
    int word = sign;
461
    for (int i = bytes.length % 4; i > 0; --i, bptr++)
462
      word = (word << 8) | (bytes[bptr] & 0xff);
463
    words[--nwords] = word;
464
 
465
    // Elements remaining in byte[] are a multiple of 4.
466
    while (nwords > 0)
467
      words[--nwords] = bytes[bptr++] << 24 |
468
                        (bytes[bptr++] & 0xff) << 16 |
469
                        (bytes[bptr++] & 0xff) << 8 |
470
                        (bytes[bptr++] & 0xff);
471
    return words;
472
  }
473
 
474
  /** Allocate a new non-shared BigInteger.
475
   * @param nwords number of words to allocate
476
   */
477
  private static BigInteger alloc(int nwords)
478
  {
479
    BigInteger result = new BigInteger();
480
    if (nwords > 1)
481
    result.words = new int[nwords];
482
    return result;
483
  }
484
 
485
  /** Change words.length to nwords.
486
   * We allow words.length to be upto nwords+2 without reallocating.
487
   */
488
  private void realloc(int nwords)
489
  {
490
    if (nwords == 0)
491
      {
492
        if (words != null)
493
          {
494
            if (ival > 0)
495
              ival = words[0];
496
            words = null;
497
          }
498
      }
499
    else if (words == null
500
             || words.length < nwords
501
             || words.length > nwords + 2)
502
      {
503
        int[] new_words = new int [nwords];
504
        if (words == null)
505
          {
506
            new_words[0] = ival;
507
            ival = 1;
508
          }
509
        else
510
          {
511
            if (nwords < ival)
512
              ival = nwords;
513
            System.arraycopy(words, 0, new_words, 0, ival);
514
          }
515
        words = new_words;
516
      }
517
  }
518
 
519
  private boolean isNegative()
520
  {
521
    return (words == null ? ival : words[ival - 1]) < 0;
522
  }
523
 
524
  public int signum()
525
  {
526
    if (USING_NATIVE)
527
      return mpz.compare(ZERO.mpz);
528
 
529
    if (ival == 0 && words == null)
530
      return 0;
531
    int top = words == null ? ival : words[ival-1];
532
    return top < 0 ? -1 : 1;
533
  }
534
 
535
  private static int compareTo(BigInteger x, BigInteger y)
536
  {
537
    if (USING_NATIVE)
538
      {
539
        int dummy = y.signum; // force NPE check
540
        return x.mpz.compare(y.mpz);
541
      }
542
 
543
    if (x.words == null && y.words == null)
544
      return x.ival < y.ival ? -1 : x.ival > y.ival ? 1 : 0;
545
    boolean x_negative = x.isNegative();
546
    boolean y_negative = y.isNegative();
547
    if (x_negative != y_negative)
548
      return x_negative ? -1 : 1;
549
    int x_len = x.words == null ? 1 : x.ival;
550
    int y_len = y.words == null ? 1 : y.ival;
551
    if (x_len != y_len)
552
      return (x_len > y_len) != x_negative ? 1 : -1;
553
    return MPN.cmp(x.words, y.words, x_len);
554
  }
555
 
556
  /** @since 1.2 */
557
  public int compareTo(BigInteger val)
558
  {
559
    return compareTo(this, val);
560
  }
561
 
562
  public BigInteger min(BigInteger val)
563
  {
564
    return compareTo(this, val) < 0 ? this : val;
565
  }
566
 
567
  public BigInteger max(BigInteger val)
568
  {
569
    return compareTo(this, val) > 0 ? this : val;
570
  }
571
 
572
  private boolean isZero()
573
  {
574
    return words == null && ival == 0;
575
  }
576
 
577
  private boolean isOne()
578
  {
579
    return words == null && ival == 1;
580
  }
581
 
582
  /** Calculate how many words are significant in words[0:len-1].
583
   * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
584
   * when words is viewed as a 2's complement integer.
585
   */
586
  private static int wordsNeeded(int[] words, int len)
587
  {
588
    int i = len;
589
    if (i > 0)
590
      {
591
        int word = words[--i];
592
        if (word == -1)
593
          {
594
            while (i > 0 && (word = words[i - 1]) < 0)
595
              {
596
                i--;
597
                if (word != -1) break;
598
              }
599
          }
600
        else
601
          {
602
            while (word == 0 && i > 0 && (word = words[i - 1]) >= 0)  i--;
603
          }
604
      }
605
    return i + 1;
606
  }
607
 
608
  private BigInteger canonicalize()
609
  {
610
    if (words != null
611
        && (ival = BigInteger.wordsNeeded(words, ival)) <= 1)
612
      {
613
        if (ival == 1)
614
          ival = words[0];
615
        words = null;
616
      }
617
    if (words == null && ival >= minFixNum && ival <= maxFixNum)
618
      return smallFixNums[ival - minFixNum];
619
    return this;
620
  }
621
 
622
  /** Add two ints, yielding a BigInteger. */
623
  private static BigInteger add(int x, int y)
624
  {
625
    return valueOf((long) x + (long) y);
626
  }
627
 
628
  /** Add a BigInteger and an int, yielding a new BigInteger. */
629
  private static BigInteger add(BigInteger x, int y)
630
  {
631
    if (x.words == null)
632
      return BigInteger.add(x.ival, y);
633
    BigInteger result = new BigInteger(0);
634
    result.setAdd(x, y);
635
    return result.canonicalize();
636
  }
637
 
638
  /** Set this to the sum of x and y.
639
   * OK if x==this. */
640
  private void setAdd(BigInteger x, int y)
641
  {
642
    if (x.words == null)
643
      {
644
        set((long) x.ival + (long) y);
645
        return;
646
      }
647
    int len = x.ival;
648
    realloc(len + 1);
649
    long carry = y;
650
    for (int i = 0;  i < len;  i++)
651
      {
652
        carry += ((long) x.words[i] & 0xffffffffL);
653
        words[i] = (int) carry;
654
        carry >>= 32;
655
      }
656
    if (x.words[len - 1] < 0)
657
      carry--;
658
    words[len] = (int) carry;
659
    ival = wordsNeeded(words, len + 1);
660
  }
661
 
662
  /** Destructively add an int to this. */
663
  private void setAdd(int y)
664
  {
665
    setAdd(this, y);
666
  }
667
 
668
  /** Destructively set the value of this to a long. */
669
  private void set(long y)
670
  {
671
    int i = (int) y;
672
    if ((long) i == y)
673
      {
674
        ival = i;
675
        words = null;
676
      }
677
    else
678
      {
679
        realloc(2);
680
        words[0] = i;
681
        words[1] = (int) (y >> 32);
682
        ival = 2;
683
      }
684
  }
685
 
686
  /** Destructively set the value of this to the given words.
687
  * The words array is reused, not copied. */
688
  private void set(int[] words, int length)
689
  {
690
    this.ival = length;
691
    this.words = words;
692
  }
693
 
694
  /** Destructively set the value of this to that of y. */
695
  private void set(BigInteger y)
696
  {
697
    if (y.words == null)
698
      set(y.ival);
699
    else if (this != y)
700
      {
701
        realloc(y.ival);
702
        System.arraycopy(y.words, 0, words, 0, y.ival);
703
        ival = y.ival;
704
      }
705
  }
706
 
707
  /** Add two BigIntegers, yielding their sum as another BigInteger. */
708
  private static BigInteger add(BigInteger x, BigInteger y, int k)
709
  {
710
    if (x.words == null && y.words == null)
711
      return valueOf((long) k * (long) y.ival + (long) x.ival);
712
    if (k != 1)
713
      {
714
        if (k == -1)
715
          y = BigInteger.neg(y);
716
        else
717
          y = BigInteger.times(y, valueOf(k));
718
      }
719
    if (x.words == null)
720
      return BigInteger.add(y, x.ival);
721
    if (y.words == null)
722
      return BigInteger.add(x, y.ival);
723
    // Both are big
724
    if (y.ival > x.ival)
725
      { // Swap so x is longer then y.
726
        BigInteger tmp = x;  x = y;  y = tmp;
727
      }
728
    BigInteger result = alloc(x.ival + 1);
729
    int i = y.ival;
730
    long carry = MPN.add_n(result.words, x.words, y.words, i);
731
    long y_ext = y.words[i - 1] < 0 ? 0xffffffffL : 0;
732
    for (; i < x.ival;  i++)
733
      {
734
        carry += ((long) x.words[i] & 0xffffffffL) + y_ext;
735
        result.words[i] = (int) carry;
736
        carry >>>= 32;
737
      }
738
    if (x.words[i - 1] < 0)
739
      y_ext--;
740
    result.words[i] = (int) (carry + y_ext);
741
    result.ival = i+1;
742
    return result.canonicalize();
743
  }
744
 
745
  public BigInteger add(BigInteger val)
746
  {
747
    if (USING_NATIVE)
748
      {
749
        int dummy = val.signum; // force NPE check
750
        BigInteger result = new BigInteger();
751
        mpz.add(val.mpz, result.mpz);
752
        return result;
753
      }
754
 
755
    return add(this, val, 1);
756
  }
757
 
758
  public BigInteger subtract(BigInteger val)
759
  {
760
    if (USING_NATIVE)
761
      {
762
        int dummy = val.signum; // force NPE check
763
        BigInteger result = new BigInteger();
764
        mpz.subtract(val.mpz, result.mpz);
765
        return result;
766
      }
767
 
768
    return add(this, val, -1);
769
  }
770
 
771
  private static BigInteger times(BigInteger x, int y)
772
  {
773
    if (y == 0)
774
      return ZERO;
775
    if (y == 1)
776
      return x;
777
    int[] xwords = x.words;
778
    int xlen = x.ival;
779
    if (xwords == null)
780
      return valueOf((long) xlen * (long) y);
781
    boolean negative;
782
    BigInteger result = BigInteger.alloc(xlen + 1);
783
    if (xwords[xlen - 1] < 0)
784
      {
785
        negative = true;
786
        negate(result.words, xwords, xlen);
787
        xwords = result.words;
788
      }
789
    else
790
      negative = false;
791
    if (y < 0)
792
      {
793
        negative = !negative;
794
        y = -y;
795
      }
796
    result.words[xlen] = MPN.mul_1(result.words, xwords, xlen, y);
797
    result.ival = xlen + 1;
798
    if (negative)
799
      result.setNegative();
800
    return result.canonicalize();
801
  }
802
 
803
  private static BigInteger times(BigInteger x, BigInteger y)
804
  {
805
    if (y.words == null)
806
      return times(x, y.ival);
807
    if (x.words == null)
808
      return times(y, x.ival);
809
    boolean negative = false;
810
    int[] xwords;
811
    int[] ywords;
812
    int xlen = x.ival;
813
    int ylen = y.ival;
814
    if (x.isNegative())
815
      {
816
        negative = true;
817
        xwords = new int[xlen];
818
        negate(xwords, x.words, xlen);
819
      }
820
    else
821
      {
822
        negative = false;
823
        xwords = x.words;
824
      }
825
    if (y.isNegative())
826
      {
827
        negative = !negative;
828
        ywords = new int[ylen];
829
        negate(ywords, y.words, ylen);
830
      }
831
    else
832
      ywords = y.words;
833
    // Swap if x is shorter then y.
834
    if (xlen < ylen)
835
      {
836
        int[] twords = xwords;  xwords = ywords;  ywords = twords;
837
        int tlen = xlen;  xlen = ylen;  ylen = tlen;
838
      }
839
    BigInteger result = BigInteger.alloc(xlen+ylen);
840
    MPN.mul(result.words, xwords, xlen, ywords, ylen);
841
    result.ival = xlen+ylen;
842
    if (negative)
843
      result.setNegative();
844
    return result.canonicalize();
845
  }
846
 
847
  public BigInteger multiply(BigInteger y)
848
  {
849
    if (USING_NATIVE)
850
      {
851
        int dummy = y.signum; // force NPE check
852
        BigInteger result = new BigInteger();
853
        mpz.multiply(y.mpz, result.mpz);
854
        return result;
855
      }
856
 
857
    return times(this, y);
858
  }
859
 
860
  private static void divide(long x, long y,
861
                             BigInteger quotient, BigInteger remainder,
862
                             int rounding_mode)
863
  {
864
    boolean xNegative, yNegative;
865
    if (x < 0)
866
      {
867
        xNegative = true;
868
        if (x == Long.MIN_VALUE)
869
          {
870
            divide(valueOf(x), valueOf(y),
871
                   quotient, remainder, rounding_mode);
872
            return;
873
          }
874
        x = -x;
875
      }
876
    else
877
      xNegative = false;
878
 
879
    if (y < 0)
880
      {
881
        yNegative = true;
882
        if (y == Long.MIN_VALUE)
883
          {
884
            if (rounding_mode == TRUNCATE)
885
              { // x != Long.Min_VALUE implies abs(x) < abs(y)
886
                if (quotient != null)
887
                  quotient.set(0);
888
                if (remainder != null)
889
                  remainder.set(x);
890
              }
891
            else
892
              divide(valueOf(x), valueOf(y),
893
                      quotient, remainder, rounding_mode);
894
            return;
895
          }
896
        y = -y;
897
      }
898
    else
899
      yNegative = false;
900
 
901
    long q = x / y;
902
    long r = x % y;
903
    boolean qNegative = xNegative ^ yNegative;
904
 
905
    boolean add_one = false;
906
    if (r != 0)
907
      {
908
        switch (rounding_mode)
909
          {
910
          case TRUNCATE:
911
            break;
912
          case CEILING:
913
          case FLOOR:
914
            if (qNegative == (rounding_mode == FLOOR))
915
              add_one = true;
916
            break;
917
          case ROUND:
918
            add_one = r > ((y - (q & 1)) >> 1);
919
            break;
920
          }
921
      }
922
    if (quotient != null)
923
      {
924
        if (add_one)
925
          q++;
926
        if (qNegative)
927
          q = -q;
928
        quotient.set(q);
929
      }
930
    if (remainder != null)
931
      {
932
        // The remainder is by definition: X-Q*Y
933
        if (add_one)
934
          {
935
            // Subtract the remainder from Y.
936
            r = y - r;
937
            // In this case, abs(Q*Y) > abs(X).
938
            // So sign(remainder) = -sign(X).
939
            xNegative = ! xNegative;
940
          }
941
        else
942
          {
943
            // If !add_one, then: abs(Q*Y) <= abs(X).
944
            // So sign(remainder) = sign(X).
945
          }
946
        if (xNegative)
947
          r = -r;
948
        remainder.set(r);
949
      }
950
  }
951
 
952
  /** Divide two integers, yielding quotient and remainder.
953
   * @param x the numerator in the division
954
   * @param y the denominator in the division
955
   * @param quotient is set to the quotient of the result (iff quotient!=null)
956
   * @param remainder is set to the remainder of the result
957
   *  (iff remainder!=null)
958
   * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
959
   */
960
  private static void divide(BigInteger x, BigInteger y,
961
                             BigInteger quotient, BigInteger remainder,
962
                             int rounding_mode)
963
  {
964
    if ((x.words == null || x.ival <= 2)
965
        && (y.words == null || y.ival <= 2))
966
      {
967
        long x_l = x.longValue();
968
        long y_l = y.longValue();
969
        if (x_l != Long.MIN_VALUE && y_l != Long.MIN_VALUE)
970
          {
971
            divide(x_l, y_l, quotient, remainder, rounding_mode);
972
            return;
973
          }
974
      }
975
 
976
    boolean xNegative = x.isNegative();
977
    boolean yNegative = y.isNegative();
978
    boolean qNegative = xNegative ^ yNegative;
979
 
980
    int ylen = y.words == null ? 1 : y.ival;
981
    int[] ywords = new int[ylen];
982
    y.getAbsolute(ywords);
983
    while (ylen > 1 && ywords[ylen - 1] == 0)  ylen--;
984
 
985
    int xlen = x.words == null ? 1 : x.ival;
986
    int[] xwords = new int[xlen+2];
987
    x.getAbsolute(xwords);
988
    while (xlen > 1 && xwords[xlen-1] == 0)  xlen--;
989
 
990
    int qlen, rlen;
991
 
992
    int cmpval = MPN.cmp(xwords, xlen, ywords, ylen);
993
    if (cmpval < 0)  // abs(x) < abs(y)
994
      { // quotient = 0;  remainder = num.
995
        int[] rwords = xwords;  xwords = ywords;  ywords = rwords;
996
        rlen = xlen;  qlen = 1;  xwords[0] = 0;
997
      }
998
    else if (cmpval == 0)  // abs(x) == abs(y)
999
      {
1000
        xwords[0] = 1;  qlen = 1;  // quotient = 1
1001
        ywords[0] = 0;  rlen = 1;  // remainder = 0;
1002
      }
1003
    else if (ylen == 1)
1004
      {
1005
        qlen = xlen;
1006
        // Need to leave room for a word of leading zeros if dividing by 1
1007
        // and the dividend has the high bit set.  It might be safe to
1008
        // increment qlen in all cases, but it certainly is only necessary
1009
        // in the following case.
1010
        if (ywords[0] == 1 && xwords[xlen-1] < 0)
1011
          qlen++;
1012
        rlen = 1;
1013
        ywords[0] = MPN.divmod_1(xwords, xwords, xlen, ywords[0]);
1014
      }
1015
    else  // abs(x) > abs(y)
1016
      {
1017
        // Normalize the denominator, i.e. make its most significant bit set by
1018
        // shifting it normalization_steps bits to the left.  Also shift the
1019
        // numerator the same number of steps (to keep the quotient the same!).
1020
 
1021
        int nshift = MPN.count_leading_zeros(ywords[ylen - 1]);
1022
        if (nshift != 0)
1023
          {
1024
            // Shift up the denominator setting the most significant bit of
1025
            // the most significant word.
1026
            MPN.lshift(ywords, 0, ywords, ylen, nshift);
1027
 
1028
            // Shift up the numerator, possibly introducing a new most
1029
            // significant word.
1030
            int x_high = MPN.lshift(xwords, 0, xwords, xlen, nshift);
1031
            xwords[xlen++] = x_high;
1032
          }
1033
 
1034
        if (xlen == ylen)
1035
          xwords[xlen++] = 0;
1036
        MPN.divide(xwords, xlen, ywords, ylen);
1037
        rlen = ylen;
1038
        MPN.rshift0 (ywords, xwords, 0, rlen, nshift);
1039
 
1040
        qlen = xlen + 1 - ylen;
1041
        if (quotient != null)
1042
          {
1043
            for (int i = 0;  i < qlen;  i++)
1044
              xwords[i] = xwords[i+ylen];
1045
          }
1046
      }
1047
 
1048
    if (ywords[rlen-1] < 0)
1049
      {
1050
        ywords[rlen] = 0;
1051
        rlen++;
1052
      }
1053
 
1054
    // Now the quotient is in xwords, and the remainder is in ywords.
1055
 
1056
    boolean add_one = false;
1057
    if (rlen > 1 || ywords[0] != 0)
1058
      { // Non-zero remainder i.e. in-exact quotient.
1059
        switch (rounding_mode)
1060
          {
1061
          case TRUNCATE:
1062
            break;
1063
          case CEILING:
1064
          case FLOOR:
1065
            if (qNegative == (rounding_mode == FLOOR))
1066
              add_one = true;
1067
            break;
1068
          case ROUND:
1069
            // int cmp = compareTo(remainder<<1, abs(y));
1070
            BigInteger tmp = remainder == null ? new BigInteger() : remainder;
1071
            tmp.set(ywords, rlen);
1072
            tmp = shift(tmp, 1);
1073
            if (yNegative)
1074
              tmp.setNegative();
1075
            int cmp = compareTo(tmp, y);
1076
            // Now cmp == compareTo(sign(y)*(remainder<<1), y)
1077
            if (yNegative)
1078
              cmp = -cmp;
1079
            add_one = (cmp == 1) || (cmp == 0 && (xwords[0]&1) != 0);
1080
          }
1081
      }
1082
    if (quotient != null)
1083
      {
1084
        quotient.set(xwords, qlen);
1085
        if (qNegative)
1086
          {
1087
            if (add_one)  // -(quotient + 1) == ~(quotient)
1088
              quotient.setInvert();
1089
            else
1090
              quotient.setNegative();
1091
          }
1092
        else if (add_one)
1093
          quotient.setAdd(1);
1094
      }
1095
    if (remainder != null)
1096
      {
1097
        // The remainder is by definition: X-Q*Y
1098
        remainder.set(ywords, rlen);
1099
        if (add_one)
1100
          {
1101
            // Subtract the remainder from Y:
1102
            // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
1103
            BigInteger tmp;
1104
            if (y.words == null)
1105
              {
1106
                tmp = remainder;
1107
                tmp.set(yNegative ? ywords[0] + y.ival : ywords[0] - y.ival);
1108
              }
1109
            else
1110
              tmp = BigInteger.add(remainder, y, yNegative ? 1 : -1);
1111
            // Now tmp <= 0.
1112
            // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
1113
            // Hence, abs(Q*Y) > abs(X).
1114
            // So sign(remainder) = -sign(X).
1115
            if (xNegative)
1116
              remainder.setNegative(tmp);
1117
            else
1118
              remainder.set(tmp);
1119
          }
1120
        else
1121
          {
1122
            // If !add_one, then: abs(Q*Y) <= abs(X).
1123
            // So sign(remainder) = sign(X).
1124
            if (xNegative)
1125
              remainder.setNegative();
1126
          }
1127
      }
1128
  }
1129
 
1130
  public BigInteger divide(BigInteger val)
1131
  {
1132
    if (USING_NATIVE)
1133
      {
1134
        if (val.compareTo(ZERO) == 0)
1135
          throw new ArithmeticException("divisor is zero");
1136
 
1137
        BigInteger result = new BigInteger();
1138
        mpz.quotient(val.mpz, result.mpz);
1139
        return result;
1140
      }
1141
 
1142
    if (val.isZero())
1143
      throw new ArithmeticException("divisor is zero");
1144
 
1145
    BigInteger quot = new BigInteger();
1146
    divide(this, val, quot, null, TRUNCATE);
1147
    return quot.canonicalize();
1148
  }
1149
 
1150
  public BigInteger remainder(BigInteger val)
1151
  {
1152
    if (USING_NATIVE)
1153
      {
1154
        if (val.compareTo(ZERO) == 0)
1155
          throw new ArithmeticException("divisor is zero");
1156
 
1157
        BigInteger result = new BigInteger();
1158
        mpz.remainder(val.mpz, result.mpz);
1159
        return result;
1160
      }
1161
 
1162
    if (val.isZero())
1163
      throw new ArithmeticException("divisor is zero");
1164
 
1165
    BigInteger rem = new BigInteger();
1166
    divide(this, val, null, rem, TRUNCATE);
1167
    return rem.canonicalize();
1168
  }
1169
 
1170
  public BigInteger[] divideAndRemainder(BigInteger val)
1171
  {
1172
    if (USING_NATIVE)
1173
      {
1174
        if (val.compareTo(ZERO) == 0)
1175
          throw new ArithmeticException("divisor is zero");
1176
 
1177
        BigInteger q = new BigInteger();
1178
        BigInteger r = new BigInteger();
1179
        mpz.quotientAndRemainder(val.mpz, q.mpz, r.mpz);
1180
        return new BigInteger[] { q, r };
1181
      }
1182
 
1183
    if (val.isZero())
1184
      throw new ArithmeticException("divisor is zero");
1185
 
1186
    BigInteger[] result = new BigInteger[2];
1187
    result[0] = new BigInteger();
1188
    result[1] = new BigInteger();
1189
    divide(this, val, result[0], result[1], TRUNCATE);
1190
    result[0].canonicalize();
1191
    result[1].canonicalize();
1192
    return result;
1193
  }
1194
 
1195
  public BigInteger mod(BigInteger m)
1196
  {
1197
    if (USING_NATIVE)
1198
      {
1199
        int dummy = m.signum; // force NPE check
1200
        if (m.compareTo(ZERO) < 1)
1201
          throw new ArithmeticException("non-positive modulus");
1202
 
1203
        BigInteger result = new BigInteger();
1204
        mpz.modulo(m.mpz, result.mpz);
1205
        return result;
1206
      }
1207
 
1208
    if (m.isNegative() || m.isZero())
1209
      throw new ArithmeticException("non-positive modulus");
1210
 
1211
    BigInteger rem = new BigInteger();
1212
    divide(this, m, null, rem, FLOOR);
1213
    return rem.canonicalize();
1214
  }
1215
 
1216
  /** Calculate the integral power of a BigInteger.
1217
   * @param exponent the exponent (must be non-negative)
1218
   */
1219
  public BigInteger pow(int exponent)
1220
  {
1221
    if (exponent <= 0)
1222
      {
1223
        if (exponent == 0)
1224
          return ONE;
1225
          throw new ArithmeticException("negative exponent");
1226
      }
1227
 
1228
    if (USING_NATIVE)
1229
      {
1230
        BigInteger result = new BigInteger();
1231
        mpz.pow(exponent, result.mpz);
1232
        return result;
1233
      }
1234
 
1235
    if (isZero())
1236
      return this;
1237
    int plen = words == null ? 1 : ival;  // Length of pow2.
1238
    int blen = ((bitLength() * exponent) >> 5) + 2 * plen;
1239
    boolean negative = isNegative() && (exponent & 1) != 0;
1240
    int[] pow2 = new int [blen];
1241
    int[] rwords = new int [blen];
1242
    int[] work = new int [blen];
1243
    getAbsolute(pow2);  // pow2 = abs(this);
1244
    int rlen = 1;
1245
    rwords[0] = 1; // rwords = 1;
1246
    for (;;)  // for (i = 0;  ; i++)
1247
      {
1248
        // pow2 == this**(2**i)
1249
        // prod = this**(sum(j=0..i-1, (exponent>>j)&1))
1250
        if ((exponent & 1) != 0)
1251
          { // r *= pow2
1252
            MPN.mul(work, pow2, plen, rwords, rlen);
1253
            int[] temp = work;  work = rwords;  rwords = temp;
1254
            rlen += plen;
1255
            while (rwords[rlen - 1] == 0)  rlen--;
1256
          }
1257
        exponent >>= 1;
1258
        if (exponent == 0)
1259
          break;
1260
        // pow2 *= pow2;
1261
        MPN.mul(work, pow2, plen, pow2, plen);
1262
        int[] temp = work;  work = pow2;  pow2 = temp;  // swap to avoid a copy
1263
        plen *= 2;
1264
        while (pow2[plen - 1] == 0)  plen--;
1265
      }
1266
    if (rwords[rlen - 1] < 0)
1267
      rlen++;
1268
    if (negative)
1269
      negate(rwords, rwords, rlen);
1270
    return BigInteger.make(rwords, rlen);
1271
  }
1272
 
1273
  private static int[] euclidInv(int a, int b, int prevDiv)
1274
  {
1275
    if (b == 0)
1276
      throw new ArithmeticException("not invertible");
1277
 
1278
    if (b == 1)
1279
        // Success:  values are indeed invertible!
1280
        // Bottom of the recursion reached; start unwinding.
1281
        return new int[] { -prevDiv, 1 };
1282
 
1283
    int[] xy = euclidInv(b, a % b, a / b);      // Recursion happens here.
1284
    a = xy[0]; // use our local copy of 'a' as a work var
1285
    xy[0] = a * -prevDiv + xy[1];
1286
    xy[1] = a;
1287
    return xy;
1288
  }
1289
 
1290
  private static void euclidInv(BigInteger a, BigInteger b,
1291
                                BigInteger prevDiv, BigInteger[] xy)
1292
  {
1293
    if (b.isZero())
1294
      throw new ArithmeticException("not invertible");
1295
 
1296
    if (b.isOne())
1297
      {
1298
        // Success:  values are indeed invertible!
1299
        // Bottom of the recursion reached; start unwinding.
1300
        xy[0] = neg(prevDiv);
1301
        xy[1] = ONE;
1302
        return;
1303
      }
1304
 
1305
    // Recursion happens in the following conditional!
1306
 
1307
    // If a just contains an int, then use integer math for the rest.
1308
    if (a.words == null)
1309
      {
1310
        int[] xyInt = euclidInv(b.ival, a.ival % b.ival, a.ival / b.ival);
1311
        xy[0] = new BigInteger(xyInt[0]);
1312
        xy[1] = new BigInteger(xyInt[1]);
1313
      }
1314
    else
1315
      {
1316
        BigInteger rem = new BigInteger();
1317
        BigInteger quot = new BigInteger();
1318
        divide(a, b, quot, rem, FLOOR);
1319
        // quot and rem may not be in canonical form. ensure
1320
        rem.canonicalize();
1321
        quot.canonicalize();
1322
        euclidInv(b, rem, quot, xy);
1323
      }
1324
 
1325
    BigInteger t = xy[0];
1326
    xy[0] = add(xy[1], times(t, prevDiv), -1);
1327
    xy[1] = t;
1328
  }
1329
 
1330
  public BigInteger modInverse(BigInteger y)
1331
  {
1332
    if (USING_NATIVE)
1333
      {
1334
        int dummy = y.signum; // force NPE check
1335
        if (mpz.compare(ZERO.mpz) < 1)
1336
          throw new ArithmeticException("non-positive modulo");
1337
 
1338
        BigInteger result = new BigInteger();
1339
        mpz.modInverse(y.mpz, result.mpz);
1340
        return result;
1341
      }
1342
 
1343
    if (y.isNegative() || y.isZero())
1344
      throw new ArithmeticException("non-positive modulo");
1345
 
1346
    // Degenerate cases.
1347
    if (y.isOne())
1348
      return ZERO;
1349
    if (isOne())
1350
      return ONE;
1351
 
1352
    // Use Euclid's algorithm as in gcd() but do this recursively
1353
    // rather than in a loop so we can use the intermediate results as we
1354
    // unwind from the recursion.
1355
    // Used http://www.math.nmsu.edu/~crypto/EuclideanAlgo.html as reference.
1356
    BigInteger result = new BigInteger();
1357
    boolean swapped = false;
1358
 
1359
    if (y.words == null)
1360
      {
1361
        // The result is guaranteed to be less than the modulus, y (which is
1362
        // an int), so simplify this by working with the int result of this
1363
        // modulo y.  Also, if this is negative, make it positive via modulo
1364
        // math.  Note that BigInteger.mod() must be used even if this is
1365
        // already an int as the % operator would provide a negative result if
1366
        // this is negative, BigInteger.mod() never returns negative values.
1367
        int xval = (words != null || isNegative()) ? mod(y).ival : ival;
1368
        int yval = y.ival;
1369
 
1370
        // Swap values so x > y.
1371
        if (yval > xval)
1372
          {
1373
            int tmp = xval; xval = yval; yval = tmp;
1374
            swapped = true;
1375
          }
1376
        // Normally, the result is in the 2nd element of the array, but
1377
        // if originally x < y, then x and y were swapped and the result
1378
        // is in the 1st element of the array.
1379
        result.ival =
1380
          euclidInv(yval, xval % yval, xval / yval)[swapped ? 0 : 1];
1381
 
1382
        // Result can't be negative, so make it positive by adding the
1383
        // original modulus, y.ival (not the possibly "swapped" yval).
1384
        if (result.ival < 0)
1385
          result.ival += y.ival;
1386
      }
1387
    else
1388
      {
1389
        // As above, force this to be a positive value via modulo math.
1390
        BigInteger x = isNegative() ? this.mod(y) : this;
1391
 
1392
        // Swap values so x > y.
1393
        if (x.compareTo(y) < 0)
1394
          {
1395
            result = x; x = y; y = result; // use 'result' as a work var
1396
            swapped = true;
1397
          }
1398
        // As above (for ints), result will be in the 2nd element unless
1399
        // the original x and y were swapped.
1400
        BigInteger rem = new BigInteger();
1401
        BigInteger quot = new BigInteger();
1402
        divide(x, y, quot, rem, FLOOR);
1403
        // quot and rem may not be in canonical form. ensure
1404
        rem.canonicalize();
1405
        quot.canonicalize();
1406
        BigInteger[] xy = new BigInteger[2];
1407
        euclidInv(y, rem, quot, xy);
1408
        result = swapped ? xy[0] : xy[1];
1409
 
1410
        // Result can't be negative, so make it positive by adding the
1411
        // original modulus, y (which is now x if they were swapped).
1412
        if (result.isNegative())
1413
          result = add(result, swapped ? x : y, 1);
1414
      }
1415
 
1416
    return result;
1417
  }
1418
 
1419
  public BigInteger modPow(BigInteger exponent, BigInteger m)
1420
  {
1421
    if (USING_NATIVE)
1422
      {
1423
        int dummy = exponent.signum; // force NPE check
1424
        if (m.mpz.compare(ZERO.mpz) < 1)
1425
          throw new ArithmeticException("non-positive modulo");
1426
 
1427
        BigInteger result = new BigInteger();
1428
        mpz.modPow(exponent.mpz, m.mpz, result.mpz);
1429
        return result;
1430
      }
1431
 
1432
    if (m.isNegative() || m.isZero())
1433
      throw new ArithmeticException("non-positive modulo");
1434
 
1435
    if (exponent.isNegative())
1436
      return modInverse(m).modPow(exponent.negate(), m);
1437
    if (exponent.isOne())
1438
      return mod(m);
1439
 
1440
    // To do this naively by first raising this to the power of exponent
1441
    // and then performing modulo m would be extremely expensive, especially
1442
    // for very large numbers.  The solution is found in Number Theory
1443
    // where a combination of partial powers and moduli can be done easily.
1444
    //
1445
    // We'll use the algorithm for Additive Chaining which can be found on
1446
    // p. 244 of "Applied Cryptography, Second Edition" by Bruce Schneier.
1447
    BigInteger s = ONE;
1448
    BigInteger t = this;
1449
    BigInteger u = exponent;
1450
 
1451
    while (!u.isZero())
1452
      {
1453
        if (u.and(ONE).isOne())
1454
          s = times(s, t).mod(m);
1455
        u = u.shiftRight(1);
1456
        t = times(t, t).mod(m);
1457
      }
1458
 
1459
    return s;
1460
  }
1461
 
1462
  /** Calculate Greatest Common Divisor for non-negative ints. */
1463
  private static int gcd(int a, int b)
1464
  {
1465
    // Euclid's algorithm, copied from libg++.
1466
    int tmp;
1467
    if (b > a)
1468
      {
1469
        tmp = a; a = b; b = tmp;
1470
      }
1471
    for(;;)
1472
      {
1473
        if (b == 0)
1474
          return a;
1475
        if (b == 1)
1476
          return b;
1477
        tmp = b;
1478
            b = a % b;
1479
            a = tmp;
1480
          }
1481
      }
1482
 
1483
  public BigInteger gcd(BigInteger y)
1484
  {
1485
    if (USING_NATIVE)
1486
      {
1487
        int dummy = y.signum; // force NPE check
1488
        BigInteger result = new BigInteger();
1489
        mpz.gcd(y.mpz, result.mpz);
1490
        return result;
1491
      }
1492
 
1493
    int xval = ival;
1494
    int yval = y.ival;
1495
    if (words == null)
1496
      {
1497
        if (xval == 0)
1498
          return abs(y);
1499
        if (y.words == null
1500
            && xval != Integer.MIN_VALUE && yval != Integer.MIN_VALUE)
1501
          {
1502
            if (xval < 0)
1503
              xval = -xval;
1504
            if (yval < 0)
1505
              yval = -yval;
1506
            return valueOf(gcd(xval, yval));
1507
          }
1508
        xval = 1;
1509
      }
1510
    if (y.words == null)
1511
      {
1512
        if (yval == 0)
1513
          return abs(this);
1514
        yval = 1;
1515
      }
1516
    int len = (xval > yval ? xval : yval) + 1;
1517
    int[] xwords = new int[len];
1518
    int[] ywords = new int[len];
1519
    getAbsolute(xwords);
1520
    y.getAbsolute(ywords);
1521
    len = MPN.gcd(xwords, ywords, len);
1522
    BigInteger result = new BigInteger(0);
1523
    result.ival = len;
1524
    result.words = xwords;
1525
    return result.canonicalize();
1526
  }
1527
 
1528
  /**
1529
   * <p>Returns <code>true</code> if this BigInteger is probably prime,
1530
   * <code>false</code> if it's definitely composite. If <code>certainty</code>
1531
   * is <code><= 0</code>, <code>true</code> is returned.</p>
1532
   *
1533
   * @param certainty a measure of the uncertainty that the caller is willing
1534
   * to tolerate: if the call returns <code>true</code> the probability that
1535
   * this BigInteger is prime exceeds <code>(1 - 1/2<sup>certainty</sup>)</code>.
1536
   * The execution time of this method is proportional to the value of this
1537
   * parameter.
1538
   * @return <code>true</code> if this BigInteger is probably prime,
1539
   * <code>false</code> if it's definitely composite.
1540
   */
1541
  public boolean isProbablePrime(int certainty)
1542
  {
1543
    if (certainty < 1)
1544
      return true;
1545
 
1546
    if (USING_NATIVE)
1547
      return mpz.testPrimality(certainty) != 0;
1548
 
1549
    /** We'll use the Rabin-Miller algorithm for doing a probabilistic
1550
     * primality test.  It is fast, easy and has faster decreasing odds of a
1551
     * composite passing than with other tests.  This means that this
1552
     * method will actually have a probability much greater than the
1553
     * 1 - .5^certainty specified in the JCL (p. 117), but I don't think
1554
     * anyone will complain about better performance with greater certainty.
1555
     *
1556
     * The Rabin-Miller algorithm can be found on pp. 259-261 of "Applied
1557
     * Cryptography, Second Edition" by Bruce Schneier.
1558
     */
1559
 
1560
    // First rule out small prime factors
1561
    BigInteger rem = new BigInteger();
1562
    int i;
1563
    for (i = 0; i < primes.length; i++)
1564
      {
1565
        if (words == null && ival == primes[i])
1566
          return true;
1567
 
1568
        divide(this, smallFixNums[primes[i] - minFixNum], null, rem, TRUNCATE);
1569
        if (rem.canonicalize().isZero())
1570
          return false;
1571
      }
1572
 
1573
    // Now perform the Rabin-Miller test.
1574
 
1575
    // Set b to the number of times 2 evenly divides (this - 1).
1576
    // I.e. 2^b is the largest power of 2 that divides (this - 1).
1577
    BigInteger pMinus1 = add(this, -1);
1578
    int b = pMinus1.getLowestSetBit();
1579
 
1580
    // Set m such that this = 1 + 2^b * m.
1581
    BigInteger m = pMinus1.divide(valueOf(2L).pow(b));
1582
 
1583
    // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Note
1584
    // 4.49 (controlling the error probability) gives the number of trials
1585
    // for an error probability of 1/2**80, given the number of bits in the
1586
    // number to test.  we shall use these numbers as is if/when 'certainty'
1587
    // is less or equal to 80, and twice as much if it's greater.
1588
    int bits = this.bitLength();
1589
    for (i = 0; i < k.length; i++)
1590
      if (bits <= k[i])
1591
        break;
1592
    int trials = t[i];
1593
    if (certainty > 80)
1594
      trials *= 2;
1595
    BigInteger z;
1596
    for (int t = 0; t < trials; t++)
1597
      {
1598
        // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al.
1599
        // Remark 4.28 states: "...A strategy that is sometimes employed
1600
        // is to fix the bases a to be the first few primes instead of
1601
        // choosing them at random.
1602
        z = smallFixNums[primes[t] - minFixNum].modPow(m, this);
1603
        if (z.isOne() || z.equals(pMinus1))
1604
          continue;                     // Passes the test; may be prime.
1605
 
1606
        for (i = 0; i < b; )
1607
          {
1608
            if (z.isOne())
1609
              return false;
1610
            i++;
1611
            if (z.equals(pMinus1))
1612
              break;                    // Passes the test; may be prime.
1613
 
1614
            z = z.modPow(valueOf(2), this);
1615
          }
1616
 
1617
        if (i == b && !z.equals(pMinus1))
1618
          return false;
1619
      }
1620
    return true;
1621
  }
1622
 
1623
  private void setInvert()
1624
  {
1625
    if (words == null)
1626
      ival = ~ival;
1627
    else
1628
      {
1629
        for (int i = ival;  --i >= 0; )
1630
          words[i] = ~words[i];
1631
      }
1632
  }
1633
 
1634
  private void setShiftLeft(BigInteger x, int count)
1635
  {
1636
    int[] xwords;
1637
    int xlen;
1638
    if (x.words == null)
1639
      {
1640
        if (count < 32)
1641
          {
1642
            set((long) x.ival << count);
1643
            return;
1644
          }
1645
        xwords = new int[1];
1646
        xwords[0] = x.ival;
1647
        xlen = 1;
1648
      }
1649
    else
1650
      {
1651
        xwords = x.words;
1652
        xlen = x.ival;
1653
      }
1654
    int word_count = count >> 5;
1655
    count &= 31;
1656
    int new_len = xlen + word_count;
1657
    if (count == 0)
1658
      {
1659
        realloc(new_len);
1660
        for (int i = xlen;  --i >= 0; )
1661
          words[i+word_count] = xwords[i];
1662
      }
1663
    else
1664
      {
1665
        new_len++;
1666
        realloc(new_len);
1667
        int shift_out = MPN.lshift(words, word_count, xwords, xlen, count);
1668
        count = 32 - count;
1669
        words[new_len-1] = (shift_out << count) >> count;  // sign-extend.
1670
      }
1671
    ival = new_len;
1672
    for (int i = word_count;  --i >= 0; )
1673
      words[i] = 0;
1674
  }
1675
 
1676
  private void setShiftRight(BigInteger x, int count)
1677
  {
1678
    if (x.words == null)
1679
      set(count < 32 ? x.ival >> count : x.ival < 0 ? -1 : 0);
1680
    else if (count == 0)
1681
      set(x);
1682
    else
1683
      {
1684
        boolean neg = x.isNegative();
1685
        int word_count = count >> 5;
1686
        count &= 31;
1687
        int d_len = x.ival - word_count;
1688
        if (d_len <= 0)
1689
          set(neg ? -1 : 0);
1690
        else
1691
          {
1692
            if (words == null || words.length < d_len)
1693
              realloc(d_len);
1694
            MPN.rshift0 (words, x.words, word_count, d_len, count);
1695
            ival = d_len;
1696
            if (neg)
1697
              words[d_len-1] |= -2 << (31 - count);
1698
          }
1699
      }
1700
  }
1701
 
1702
  private void setShift(BigInteger x, int count)
1703
  {
1704
    if (count > 0)
1705
      setShiftLeft(x, count);
1706
    else
1707
      setShiftRight(x, -count);
1708
  }
1709
 
1710
  private static BigInteger shift(BigInteger x, int count)
1711
  {
1712
    if (x.words == null)
1713
      {
1714
        if (count <= 0)
1715
          return valueOf(count > -32 ? x.ival >> (-count) : x.ival < 0 ? -1 : 0);
1716
        if (count < 32)
1717
          return valueOf((long) x.ival << count);
1718
      }
1719
    if (count == 0)
1720
      return x;
1721
    BigInteger result = new BigInteger(0);
1722
    result.setShift(x, count);
1723
    return result.canonicalize();
1724
  }
1725
 
1726
  public BigInteger shiftLeft(int n)
1727
  {
1728
    if (n == 0)
1729
      return this;
1730
 
1731
    if (USING_NATIVE)
1732
      {
1733
        BigInteger result = new BigInteger();
1734
        if (n < 0)
1735
          mpz.shiftRight(-n, result.mpz);
1736
        else
1737
          mpz.shiftLeft(n, result.mpz);
1738
        return result;
1739
      }
1740
 
1741
    return shift(this, n);
1742
  }
1743
 
1744
  public BigInteger shiftRight(int n)
1745
  {
1746
    if (n == 0)
1747
      return this;
1748
 
1749
    if (USING_NATIVE)
1750
      {
1751
        BigInteger result = new BigInteger();
1752
        if (n < 0)
1753
          mpz.shiftLeft(-n, result.mpz);
1754
        else
1755
          mpz.shiftRight(n, result.mpz);
1756
        return result;
1757
      }
1758
 
1759
    return shift(this, -n);
1760
  }
1761
 
1762
  private void format(int radix, CPStringBuilder buffer)
1763
  {
1764
    if (words == null)
1765
      buffer.append(Integer.toString(ival, radix));
1766
    else if (ival <= 2)
1767
      buffer.append(Long.toString(longValue(), radix));
1768
    else
1769
      {
1770
        boolean neg = isNegative();
1771
        int[] work;
1772
        if (neg || radix != 16)
1773
          {
1774
            work = new int[ival];
1775
            getAbsolute(work);
1776
          }
1777
        else
1778
          work = words;
1779
        int len = ival;
1780
 
1781
        if (radix == 16)
1782
          {
1783
            if (neg)
1784
              buffer.append('-');
1785
            int buf_start = buffer.length();
1786
            for (int i = len;  --i >= 0; )
1787
              {
1788
                int word = work[i];
1789
                for (int j = 8;  --j >= 0; )
1790
                  {
1791
                    int hex_digit = (word >> (4 * j)) & 0xF;
1792
                    // Suppress leading zeros:
1793
                    if (hex_digit > 0 || buffer.length() > buf_start)
1794
                      buffer.append(Character.forDigit(hex_digit, 16));
1795
                  }
1796
              }
1797
          }
1798
        else
1799
          {
1800
            int i = buffer.length();
1801
            for (;;)
1802
              {
1803
                int digit = MPN.divmod_1(work, work, len, radix);
1804
                buffer.append(Character.forDigit(digit, radix));
1805
                while (len > 0 && work[len-1] == 0) len--;
1806
                if (len == 0)
1807
                  break;
1808
              }
1809
            if (neg)
1810
              buffer.append('-');
1811
            /* Reverse buffer. */
1812
            int j = buffer.length() - 1;
1813
            while (i < j)
1814
              {
1815
                char tmp = buffer.charAt(i);
1816
                buffer.setCharAt(i, buffer.charAt(j));
1817
                buffer.setCharAt(j, tmp);
1818
                i++;  j--;
1819
              }
1820
          }
1821
      }
1822
  }
1823
 
1824
  public String toString()
1825
  {
1826
    return toString(10);
1827
  }
1828
 
1829
  public String toString(int radix)
1830
  {
1831
    if (USING_NATIVE)
1832
      return mpz.toString(radix);
1833
 
1834
    if (words == null)
1835
      return Integer.toString(ival, radix);
1836
    if (ival <= 2)
1837
      return Long.toString(longValue(), radix);
1838
    int buf_size = ival * (MPN.chars_per_word(radix) + 1);
1839
    CPStringBuilder buffer = new CPStringBuilder(buf_size);
1840
    format(radix, buffer);
1841
    return buffer.toString();
1842
  }
1843
 
1844
  public int intValue()
1845
  {
1846
    if (USING_NATIVE)
1847
      {
1848
        int result = mpz.absIntValue();
1849
        return mpz.compare(ZERO.mpz) < 0 ? - result : result;
1850
      }
1851
 
1852
    if (words == null)
1853
      return ival;
1854
    return words[0];
1855
  }
1856
 
1857
  public long longValue()
1858
  {
1859
    if (USING_NATIVE)
1860
      {
1861
        long result;
1862
        result = (abs().shiftRight(32)).mpz.absIntValue();
1863
        result <<= 32;
1864
        result |= mpz.absIntValue() & 0xFFFFFFFFL;
1865
        return this.compareTo(ZERO) < 0 ? - result : result;
1866
      }
1867
 
1868
    if (words == null)
1869
      return ival;
1870
    if (ival == 1)
1871
      return words[0];
1872
    return ((long)words[1] << 32) + ((long)words[0] & 0xffffffffL);
1873
  }
1874
 
1875
  public int hashCode()
1876
  {
1877
    // FIXME: May not match hashcode of JDK.
1878
    if (USING_NATIVE)
1879
      {
1880
        // TODO: profile to decide whether to make it native
1881
        byte[] bytes = this.toByteArray();
1882
        int result = 0;
1883
        for (int i = 0; i < bytes.length; i++)
1884
          result ^= (bytes[i] & 0xFF) << (8 * (i % 4));
1885
        return result;
1886
      }
1887
 
1888
    return words == null ? ival : (words[0] + words[ival - 1]);
1889
  }
1890
 
1891
  /* Assumes x and y are both canonicalized. */
1892
  private static boolean equals(BigInteger x, BigInteger y)
1893
  {
1894
    if (USING_NATIVE)
1895
      return x.mpz.compare(y.mpz) == 0;
1896
 
1897
    if (x.words == null && y.words == null)
1898
      return x.ival == y.ival;
1899
    if (x.words == null || y.words == null || x.ival != y.ival)
1900
      return false;
1901
    for (int i = x.ival; --i >= 0; )
1902
      {
1903
        if (x.words[i] != y.words[i])
1904
          return false;
1905
      }
1906
    return true;
1907
  }
1908
 
1909
  /* Assumes this and obj are both canonicalized. */
1910
  public boolean equals(Object obj)
1911
  {
1912
    if (! (obj instanceof BigInteger))
1913
      return false;
1914
    return equals(this, (BigInteger) obj);
1915
  }
1916
 
1917
  private static BigInteger valueOf(byte[] digits, int byte_len,
1918
                                    boolean negative, int radix)
1919
  {
1920
    int chars_per_word = MPN.chars_per_word(radix);
1921
    int[] words = new int[byte_len / chars_per_word + 1];
1922
    int size = MPN.set_str(words, digits, byte_len, radix);
1923
    if (size == 0)
1924
      return ZERO;
1925
    if (words[size-1] < 0)
1926
      words[size++] = 0;
1927
    if (negative)
1928
      negate(words, words, size);
1929
    return make(words, size);
1930
  }
1931
 
1932
  public double doubleValue()
1933
  {
1934
    if (USING_NATIVE)
1935
      return mpz.doubleValue();
1936
 
1937
    if (words == null)
1938
      return (double) ival;
1939
    if (ival <= 2)
1940
      return (double) longValue();
1941
    if (isNegative())
1942
      return neg(this).roundToDouble(0, true, false);
1943
      return roundToDouble(0, false, false);
1944
  }
1945
 
1946
  public float floatValue()
1947
  {
1948
    return (float) doubleValue();
1949
  }
1950
 
1951
  /** Return true if any of the lowest n bits are one.
1952
   * (false if n is negative).  */
1953
  private boolean checkBits(int n)
1954
  {
1955
    if (n <= 0)
1956
      return false;
1957
    if (words == null)
1958
      return n > 31 || ((ival & ((1 << n) - 1)) != 0);
1959
    int i;
1960
    for (i = 0; i < (n >> 5) ; i++)
1961
      if (words[i] != 0)
1962
        return true;
1963
    return (n & 31) != 0 && (words[i] & ((1 << (n & 31)) - 1)) != 0;
1964
  }
1965
 
1966
  /** Convert a semi-processed BigInteger to double.
1967
   * Number must be non-negative.  Multiplies by a power of two, applies sign,
1968
   * and converts to double, with the usual java rounding.
1969
   * @param exp power of two, positive or negative, by which to multiply
1970
   * @param neg true if negative
1971
   * @param remainder true if the BigInteger is the result of a truncating
1972
   * division that had non-zero remainder.  To ensure proper rounding in
1973
   * this case, the BigInteger must have at least 54 bits.  */
1974
  private double roundToDouble(int exp, boolean neg, boolean remainder)
1975
  {
1976
    // Compute length.
1977
    int il = bitLength();
1978
 
1979
    // Exponent when normalized to have decimal point directly after
1980
    // leading one.  This is stored excess 1023 in the exponent bit field.
1981
    exp += il - 1;
1982
 
1983
    // Gross underflow.  If exp == -1075, we let the rounding
1984
    // computation determine whether it is minval or 0 (which are just
1985
    // 0x0000 0000 0000 0001 and 0x0000 0000 0000 0000 as bit
1986
    // patterns).
1987
    if (exp < -1075)
1988
      return neg ? -0.0 : 0.0;
1989
 
1990
    // gross overflow
1991
    if (exp > 1023)
1992
      return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1993
 
1994
    // number of bits in mantissa, including the leading one.
1995
    // 53 unless it's denormalized
1996
    int ml = (exp >= -1022 ? 53 : 53 + exp + 1022);
1997
 
1998
    // Get top ml + 1 bits.  The extra one is for rounding.
1999
    long m;
2000
    int excess_bits = il - (ml + 1);
2001
    if (excess_bits > 0)
2002
      m = ((words == null) ? ival >> excess_bits
2003
           : MPN.rshift_long(words, ival, excess_bits));
2004
    else
2005
      m = longValue() << (- excess_bits);
2006
 
2007
    // Special rounding for maxval.  If the number exceeds maxval by
2008
    // any amount, even if it's less than half a step, it overflows.
2009
    if (exp == 1023 && ((m >> 1) == (1L << 53) - 1))
2010
      {
2011
        if (remainder || checkBits(il - ml))
2012
          return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
2013
        else
2014
          return neg ? - Double.MAX_VALUE : Double.MAX_VALUE;
2015
      }
2016
 
2017
    // Normal round-to-even rule: round up if the bit dropped is a one, and
2018
    // the bit above it or any of the bits below it is a one.
2019
    if ((m & 1) == 1
2020
        && ((m & 2) == 2 || remainder || checkBits(excess_bits)))
2021
      {
2022
        m += 2;
2023
        // Check if we overflowed the mantissa
2024
        if ((m & (1L << 54)) != 0)
2025
          {
2026
            exp++;
2027
            // renormalize
2028
            m >>= 1;
2029
          }
2030
        // Check if a denormalized mantissa was just rounded up to a
2031
        // normalized one.
2032
        else if (ml == 52 && (m & (1L << 53)) != 0)
2033
          exp++;
2034
      }
2035
 
2036
    // Discard the rounding bit
2037
    m >>= 1;
2038
 
2039
    long bits_sign = neg ? (1L << 63) : 0;
2040
    exp += 1023;
2041
    long bits_exp = (exp <= 0) ? 0 : ((long)exp) << 52;
2042
    long bits_mant = m & ~(1L << 52);
2043
    return Double.longBitsToDouble(bits_sign | bits_exp | bits_mant);
2044
  }
2045
 
2046
  /** Copy the abolute value of this into an array of words.
2047
   * Assumes words.length >= (this.words == null ? 1 : this.ival).
2048
   * Result is zero-extended, but need not be a valid 2's complement number.
2049
   */
2050
  private void getAbsolute(int[] words)
2051
  {
2052
    int len;
2053
    if (this.words == null)
2054
      {
2055
        len = 1;
2056
        words[0] = this.ival;
2057
      }
2058
    else
2059
      {
2060
        len = this.ival;
2061
        for (int i = len;  --i >= 0; )
2062
          words[i] = this.words[i];
2063
      }
2064
    if (words[len - 1] < 0)
2065
      negate(words, words, len);
2066
    for (int i = words.length;  --i > len; )
2067
      words[i] = 0;
2068
  }
2069
 
2070
  /** Set dest[0:len-1] to the negation of src[0:len-1].
2071
   * Return true if overflow (i.e. if src is -2**(32*len-1)).
2072
   * Ok for src==dest. */
2073
  private static boolean negate(int[] dest, int[] src, int len)
2074
  {
2075
    long carry = 1;
2076
    boolean negative = src[len-1] < 0;
2077
    for (int i = 0;  i < len;  i++)
2078
      {
2079
        carry += ((long) (~src[i]) & 0xffffffffL);
2080
        dest[i] = (int) carry;
2081
        carry >>= 32;
2082
      }
2083
    return (negative && dest[len-1] < 0);
2084
  }
2085
 
2086
  /** Destructively set this to the negative of x.
2087
   * It is OK if x==this.*/
2088
  private void setNegative(BigInteger x)
2089
  {
2090
    int len = x.ival;
2091
    if (x.words == null)
2092
      {
2093
        if (len == Integer.MIN_VALUE)
2094
          set(- (long) len);
2095
        else
2096
          set(-len);
2097
        return;
2098
      }
2099
    realloc(len + 1);
2100
    if (negate(words, x.words, len))
2101
      words[len++] = 0;
2102
    ival = len;
2103
  }
2104
 
2105
  /** Destructively negate this. */
2106
  private void setNegative()
2107
  {
2108
    setNegative(this);
2109
  }
2110
 
2111
  private static BigInteger abs(BigInteger x)
2112
  {
2113
    return x.isNegative() ? neg(x) : x;
2114
  }
2115
 
2116
  public BigInteger abs()
2117
  {
2118
    if (USING_NATIVE)
2119
      {
2120
        BigInteger result = new BigInteger();
2121
        mpz.abs(result.mpz);
2122
        return result;
2123
      }
2124
 
2125
    return abs(this);
2126
  }
2127
 
2128
  private static BigInteger neg(BigInteger x)
2129
  {
2130
    if (x.words == null && x.ival != Integer.MIN_VALUE)
2131
      return valueOf(- x.ival);
2132
    BigInteger result = new BigInteger(0);
2133
    result.setNegative(x);
2134
    return result.canonicalize();
2135
  }
2136
 
2137
  public BigInteger negate()
2138
  {
2139
    if (USING_NATIVE)
2140
      {
2141
        BigInteger result = new BigInteger();
2142
        mpz.negate(result.mpz);
2143
        return result;
2144
      }
2145
 
2146
    return neg(this);
2147
  }
2148
 
2149
  /** Calculates ceiling(log2(this < 0 ? -this : this+1))
2150
   * See Common Lisp: the Language, 2nd ed, p. 361.
2151
   */
2152
  public int bitLength()
2153
  {
2154
    if (USING_NATIVE)
2155
      return mpz.bitLength();
2156
 
2157
    if (words == null)
2158
      return MPN.intLength(ival);
2159
      return MPN.intLength(words, ival);
2160
  }
2161
 
2162
  public byte[] toByteArray()
2163
  {
2164
    if (signum() == 0)
2165
      return new byte[1];
2166
 
2167
    if (USING_NATIVE)
2168
      {
2169
        // the minimal number of bytes required to represent the MPI is function
2170
        // of (a) its bit-length, and (b) its sign.  only when this MPI is both
2171
        // positive, and its bit-length is a multiple of 8 do we add one zero
2172
        // bit for its sign.  we do this so if we construct a new MPI from the
2173
        // resulting byte array, we wouldn't mistake a positive number, whose
2174
        // bit-length is a multiple of 8, for a similar-length negative one.
2175
        int bits = bitLength();
2176
        if (bits % 8 == 0 || this.signum() == 1)
2177
          bits++;
2178
        byte[] bytes = new byte[(bits + 7) / 8];
2179
        mpz.toByteArray(bytes);
2180
        return bytes;
2181
      }
2182
 
2183
    // Determine number of bytes needed.  The method bitlength returns
2184
    // the size without the sign bit, so add one bit for that and then
2185
    // add 7 more to emulate the ceil function using integer math.
2186
    byte[] bytes = new byte[(bitLength() + 1 + 7) / 8];
2187
    int nbytes = bytes.length;
2188
 
2189
    int wptr = 0;
2190
    int word;
2191
 
2192
    // Deal with words array until one word or less is left to process.
2193
    // If BigInteger is an int, then it is in ival and nbytes will be <= 4.
2194
    while (nbytes > 4)
2195
      {
2196
        word = words[wptr++];
2197
        for (int i = 4; i > 0; --i, word >>= 8)
2198
          bytes[--nbytes] = (byte) word;
2199
      }
2200
 
2201
    // Deal with the last few bytes.  If BigInteger is an int, use ival.
2202
    word = (words == null) ? ival : words[wptr];
2203
    for ( ; nbytes > 0; word >>= 8)
2204
      bytes[--nbytes] = (byte) word;
2205
 
2206
    return bytes;
2207
  }
2208
 
2209
  /** Return the boolean opcode (for bitOp) for swapped operands.
2210
   * I.e. bitOp(swappedOp(op), x, y) == bitOp(op, y, x).
2211
   */
2212
  private static int swappedOp(int op)
2213
  {
2214
    return
2215
    "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
2216
    .charAt(op);
2217
  }
2218
 
2219
  /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
2220
  private static BigInteger bitOp(int op, BigInteger x, BigInteger y)
2221
  {
2222
    switch (op)
2223
      {
2224
        case 0:  return ZERO;
2225
        case 1:  return x.and(y);
2226
        case 3:  return x;
2227
        case 5:  return y;
2228
        case 15: return valueOf(-1);
2229
      }
2230
    BigInteger result = new BigInteger();
2231
    setBitOp(result, op, x, y);
2232
    return result.canonicalize();
2233
  }
2234
 
2235
  /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
2236
  private static void setBitOp(BigInteger result, int op,
2237
                               BigInteger x, BigInteger y)
2238
  {
2239
    if ((y.words != null) && (x.words == null || x.ival < y.ival))
2240
      {
2241
        BigInteger temp = x;  x = y;  y = temp;
2242
        op = swappedOp(op);
2243
      }
2244
    int xi;
2245
    int yi;
2246
    int xlen, ylen;
2247
    if (y.words == null)
2248
      {
2249
        yi = y.ival;
2250
        ylen = 1;
2251
      }
2252
    else
2253
      {
2254
        yi = y.words[0];
2255
        ylen = y.ival;
2256
      }
2257
    if (x.words == null)
2258
      {
2259
        xi = x.ival;
2260
        xlen = 1;
2261
      }
2262
    else
2263
      {
2264
        xi = x.words[0];
2265
        xlen = x.ival;
2266
      }
2267
    if (xlen > 1)
2268
      result.realloc(xlen);
2269
    int[] w = result.words;
2270
    int i = 0;
2271
    // Code for how to handle the remainder of x.
2272
    // 0:  Truncate to length of y.
2273
    // 1:  Copy rest of x.
2274
    // 2:  Invert rest of x.
2275
    int finish = 0;
2276
    int ni;
2277
    switch (op)
2278
      {
2279
      case 0:  // clr
2280
        ni = 0;
2281
        break;
2282
      case 1: // and
2283
        for (;;)
2284
          {
2285
            ni = xi & yi;
2286
            if (i+1 >= ylen) break;
2287
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2288
          }
2289
        if (yi < 0) finish = 1;
2290
        break;
2291
      case 2: // andc2
2292
        for (;;)
2293
          {
2294
            ni = xi & ~yi;
2295
            if (i+1 >= ylen) break;
2296
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2297
          }
2298
        if (yi >= 0) finish = 1;
2299
        break;
2300
      case 3:  // copy x
2301
        ni = xi;
2302
        finish = 1;  // Copy rest
2303
        break;
2304
      case 4: // andc1
2305
        for (;;)
2306
          {
2307
            ni = ~xi & yi;
2308
            if (i+1 >= ylen) break;
2309
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2310
          }
2311
        if (yi < 0) finish = 2;
2312
        break;
2313
      case 5: // copy y
2314
        for (;;)
2315
          {
2316
            ni = yi;
2317
            if (i+1 >= ylen) break;
2318
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2319
          }
2320
        break;
2321
      case 6:  // xor
2322
        for (;;)
2323
          {
2324
            ni = xi ^ yi;
2325
            if (i+1 >= ylen) break;
2326
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2327
          }
2328
        finish = yi < 0 ? 2 : 1;
2329
        break;
2330
      case 7:  // ior
2331
        for (;;)
2332
          {
2333
            ni = xi | yi;
2334
            if (i+1 >= ylen) break;
2335
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2336
          }
2337
        if (yi >= 0) finish = 1;
2338
        break;
2339
      case 8:  // nor
2340
        for (;;)
2341
          {
2342
            ni = ~(xi | yi);
2343
            if (i+1 >= ylen) break;
2344
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2345
          }
2346
        if (yi >= 0)  finish = 2;
2347
        break;
2348
      case 9:  // eqv [exclusive nor]
2349
        for (;;)
2350
          {
2351
            ni = ~(xi ^ yi);
2352
            if (i+1 >= ylen) break;
2353
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2354
          }
2355
        finish = yi >= 0 ? 2 : 1;
2356
        break;
2357
      case 10:  // c2
2358
        for (;;)
2359
          {
2360
            ni = ~yi;
2361
            if (i+1 >= ylen) break;
2362
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2363
          }
2364
        break;
2365
      case 11:  // orc2
2366
        for (;;)
2367
          {
2368
            ni = xi | ~yi;
2369
            if (i+1 >= ylen) break;
2370
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2371
          }
2372
        if (yi < 0)  finish = 1;
2373
        break;
2374
      case 12:  // c1
2375
        ni = ~xi;
2376
        finish = 2;
2377
        break;
2378
      case 13:  // orc1
2379
        for (;;)
2380
          {
2381
            ni = ~xi | yi;
2382
            if (i+1 >= ylen) break;
2383
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2384
          }
2385
        if (yi >= 0) finish = 2;
2386
        break;
2387
      case 14:  // nand
2388
        for (;;)
2389
          {
2390
            ni = ~(xi & yi);
2391
            if (i+1 >= ylen) break;
2392
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2393
          }
2394
        if (yi < 0) finish = 2;
2395
        break;
2396
      default:
2397
      case 15:  // set
2398
        ni = -1;
2399
        break;
2400
      }
2401
    // Here i==ylen-1; w[0]..w[i-1] have the correct result;
2402
    // and ni contains the correct result for w[i+1].
2403
    if (i+1 == xlen)
2404
      finish = 0;
2405
    switch (finish)
2406
      {
2407
      case 0:
2408
        if (i == 0 && w == null)
2409
          {
2410
            result.ival = ni;
2411
            return;
2412
          }
2413
        w[i++] = ni;
2414
        break;
2415
      case 1:  w[i] = ni;  while (++i < xlen)  w[i] = x.words[i];  break;
2416
      case 2:  w[i] = ni;  while (++i < xlen)  w[i] = ~x.words[i];  break;
2417
      }
2418
    result.ival = i;
2419
  }
2420
 
2421
  /** Return the logical (bit-wise) "and" of a BigInteger and an int. */
2422
  private static BigInteger and(BigInteger x, int y)
2423
  {
2424
    if (x.words == null)
2425
      return valueOf(x.ival & y);
2426
    if (y >= 0)
2427
      return valueOf(x.words[0] & y);
2428
    int len = x.ival;
2429
    int[] words = new int[len];
2430
    words[0] = x.words[0] & y;
2431
    while (--len > 0)
2432
      words[len] = x.words[len];
2433
    return make(words, x.ival);
2434
  }
2435
 
2436
  /** Return the logical (bit-wise) "and" of two BigIntegers. */
2437
  public BigInteger and(BigInteger y)
2438
  {
2439
    if (USING_NATIVE)
2440
      {
2441
        int dummy = y.signum; // force NPE check
2442
        BigInteger result = new BigInteger();
2443
        mpz.and(y.mpz, result.mpz);
2444
        return result;
2445
      }
2446
 
2447
    if (y.words == null)
2448
      return and(this, y.ival);
2449
    else if (words == null)
2450
      return and(y, ival);
2451
 
2452
    BigInteger x = this;
2453
    if (ival < y.ival)
2454
      {
2455
        BigInteger temp = this;  x = y;  y = temp;
2456
      }
2457
    int i;
2458
    int len = y.isNegative() ? x.ival : y.ival;
2459
    int[] words = new int[len];
2460
    for (i = 0;  i < y.ival;  i++)
2461
      words[i] = x.words[i] & y.words[i];
2462
    for ( ; i < len;  i++)
2463
      words[i] = x.words[i];
2464
    return make(words, len);
2465
  }
2466
 
2467
  /** Return the logical (bit-wise) "(inclusive) or" of two BigIntegers. */
2468
  public BigInteger or(BigInteger y)
2469
  {
2470
    if (USING_NATIVE)
2471
      {
2472
        int dummy = y.signum; // force NPE check
2473
        BigInteger result = new BigInteger();
2474
        mpz.or(y.mpz, result.mpz);
2475
        return result;
2476
      }
2477
 
2478
    return bitOp(7, this, y);
2479
  }
2480
 
2481
  /** Return the logical (bit-wise) "exclusive or" of two BigIntegers. */
2482
  public BigInteger xor(BigInteger y)
2483
  {
2484
    if (USING_NATIVE)
2485
      {
2486
        int dummy = y.signum; // force NPE check
2487
        BigInteger result = new BigInteger();
2488
        mpz.xor(y.mpz, result.mpz);
2489
        return result;
2490
      }
2491
 
2492
    return bitOp(6, this, y);
2493
  }
2494
 
2495
  /** Return the logical (bit-wise) negation of a BigInteger. */
2496
  public BigInteger not()
2497
  {
2498
    if (USING_NATIVE)
2499
      {
2500
        BigInteger result = new BigInteger();
2501
        mpz.not(result.mpz);
2502
        return result;
2503
      }
2504
 
2505
    return bitOp(12, this, ZERO);
2506
  }
2507
 
2508
  public BigInteger andNot(BigInteger val)
2509
  {
2510
    if (USING_NATIVE)
2511
      {
2512
        int dummy = val.signum; // force NPE check
2513
        BigInteger result = new BigInteger();
2514
        mpz.andNot(val.mpz, result.mpz);
2515
        return result;
2516
      }
2517
 
2518
    return and(val.not());
2519
  }
2520
 
2521
  public BigInteger clearBit(int n)
2522
  {
2523
    if (n < 0)
2524
      throw new ArithmeticException();
2525
 
2526
    if (USING_NATIVE)
2527
      {
2528
        BigInteger result = new BigInteger();
2529
        mpz.setBit(n, false, result.mpz);
2530
        return result;
2531
      }
2532
 
2533
    return and(ONE.shiftLeft(n).not());
2534
  }
2535
 
2536
  public BigInteger setBit(int n)
2537
  {
2538
    if (n < 0)
2539
      throw new ArithmeticException();
2540
 
2541
    if (USING_NATIVE)
2542
      {
2543
        BigInteger result = new BigInteger();
2544
        mpz.setBit(n, true, result.mpz);
2545
        return result;
2546
      }
2547
 
2548
    return or(ONE.shiftLeft(n));
2549
  }
2550
 
2551
  public boolean testBit(int n)
2552
  {
2553
    if (n < 0)
2554
      throw new ArithmeticException();
2555
 
2556
    if (USING_NATIVE)
2557
      return mpz.testBit(n) != 0;
2558
 
2559
    return !and(ONE.shiftLeft(n)).isZero();
2560
  }
2561
 
2562
  public BigInteger flipBit(int n)
2563
  {
2564
    if (n < 0)
2565
      throw new ArithmeticException();
2566
 
2567
    if (USING_NATIVE)
2568
      {
2569
        BigInteger result = new BigInteger();
2570
        mpz.flipBit(n, result.mpz);
2571
        return result;
2572
      }
2573
 
2574
    return xor(ONE.shiftLeft(n));
2575
  }
2576
 
2577
  public int getLowestSetBit()
2578
  {
2579
    if (USING_NATIVE)
2580
      return mpz.compare(ZERO.mpz) == 0 ? -1 : mpz.lowestSetBit();
2581
 
2582
    if (isZero())
2583
      return -1;
2584
 
2585
    if (words == null)
2586
      return MPN.findLowestBit(ival);
2587
    else
2588
      return MPN.findLowestBit(words);
2589
  }
2590
 
2591
  // bit4count[I] is number of '1' bits in I.
2592
  private static final byte[] bit4_count = { 0, 1, 1, 2,  1, 2, 2, 3,
2593
                                             1, 2, 2, 3,  2, 3, 3, 4};
2594
 
2595
  private static int bitCount(int i)
2596
  {
2597
    int count = 0;
2598
    while (i != 0)
2599
      {
2600
        count += bit4_count[i & 15];
2601
        i >>>= 4;
2602
      }
2603
    return count;
2604
  }
2605
 
2606
  private static int bitCount(int[] x, int len)
2607
  {
2608
    int count = 0;
2609
    while (--len >= 0)
2610
      count += bitCount(x[len]);
2611
    return count;
2612
  }
2613
 
2614
  /** Count one bits in a BigInteger.
2615
   * If argument is negative, count zero bits instead. */
2616
  public int bitCount()
2617
  {
2618
    if (USING_NATIVE)
2619
      return mpz.bitCount();
2620
 
2621
    int i, x_len;
2622
    int[] x_words = words;
2623
    if (x_words == null)
2624
      {
2625
        x_len = 1;
2626
        i = bitCount(ival);
2627
      }
2628
    else
2629
      {
2630
        x_len = ival;
2631
        i = bitCount(x_words, x_len);
2632
      }
2633
    return isNegative() ? x_len * 32 - i : i;
2634
  }
2635
 
2636
  private void readObject(ObjectInputStream s)
2637
    throws IOException, ClassNotFoundException
2638
  {
2639
    if (USING_NATIVE)
2640
      {
2641
        mpz = new GMP();
2642
        s.defaultReadObject();
2643
        if (signum != 0)
2644
          mpz.fromByteArray(magnitude);
2645
        // else it's zero and we need to do nothing
2646
      }
2647
    else
2648
      {
2649
        s.defaultReadObject();
2650
        if (magnitude.length == 0 || signum == 0)
2651
          {
2652
            this.ival = 0;
2653
            this.words = null;
2654
          }
2655
        else
2656
          {
2657
            words = byteArrayToIntArray(magnitude, signum < 0 ? -1 : 0);
2658
            BigInteger result = make(words, words.length);
2659
            this.ival = result.ival;
2660
            this.words = result.words;
2661
          }
2662
      }
2663
  }
2664
 
2665
  private void writeObject(ObjectOutputStream s)
2666
    throws IOException, ClassNotFoundException
2667
  {
2668
    signum = signum();
2669
    magnitude = signum == 0 ? new byte[0] : toByteArray();
2670
    s.defaultWriteObject();
2671
    magnitude = null; // not needed anymore
2672
  }
2673
 
2674
  // inner class(es) ..........................................................
2675
 
2676
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.