1/*
2 * Copyright (C) 2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package java.math;
18
19/*
20 * In contrast to BigIntegers this class doesn't fake two's complement representation.
21 * Any Bit-Operations, including Shifting, solely regard the unsigned magnitude.
22 * Moreover BigInt objects are mutable and offer efficient in-place-operations.
23 */
24final class BigInt {
25
26    /* Fields used for the internal representation. */
27    transient long bignum = 0;
28
29    @Override protected void finalize() throws Throwable {
30        try {
31            if (this.bignum != 0) {
32                NativeBN.BN_free(this.bignum);
33                this.bignum = 0;
34            }
35        } finally {
36            super.finalize();
37        }
38    }
39
40    @Override
41    public String toString() {
42        return this.decString();
43    }
44
45    long getNativeBIGNUM() {
46        return this.bignum;
47    }
48
49    private void makeValid() {
50        if (this.bignum == 0) {
51            this.bignum = NativeBN.BN_new();
52        }
53    }
54
55    private static BigInt newBigInt() {
56        BigInt bi = new BigInt();
57        bi.bignum = NativeBN.BN_new();
58        return bi;
59    }
60
61
62    static int cmp(BigInt a, BigInt b) {
63        return NativeBN.BN_cmp(a.bignum, b.bignum);
64    }
65
66
67    void putCopy(BigInt from) {
68        this.makeValid();
69        NativeBN.BN_copy(this.bignum, from.bignum);
70    }
71
72    BigInt copy() {
73        BigInt bi = new BigInt();
74        bi.putCopy(this);
75        return bi;
76    }
77
78
79    void putLongInt(long val) {
80        this.makeValid();
81        NativeBN.putLongInt(this.bignum, val);
82    }
83
84    void putULongInt(long val, boolean neg) {
85        this.makeValid();
86        NativeBN.putULongInt(this.bignum, val, neg);
87    }
88
89    private NumberFormatException invalidBigInteger(String s) {
90        throw new NumberFormatException("Invalid BigInteger: " + s);
91    }
92
93    void putDecString(String original) {
94        String s = checkString(original, 10);
95        this.makeValid();
96        int usedLen = NativeBN.BN_dec2bn(this.bignum, s);
97        if (usedLen < s.length()) {
98            throw invalidBigInteger(original);
99        }
100    }
101
102    void putHexString(String original) {
103        String s = checkString(original, 16);
104        this.makeValid();
105        int usedLen = NativeBN.BN_hex2bn(this.bignum, s);
106        if (usedLen < s.length()) {
107            throw invalidBigInteger(original);
108        }
109    }
110
111    /**
112     * Returns a string suitable for passing to OpenSSL.
113     * Throws if 's' doesn't match Java's rules for valid BigInteger strings.
114     * BN_dec2bn and BN_hex2bn do very little checking, so we need to manually
115     * ensure we comply with Java's rules.
116     * http://code.google.com/p/android/issues/detail?id=7036
117     */
118    String checkString(String s, int base) {
119        if (s == null) {
120            throw new NullPointerException("s == null");
121        }
122        // A valid big integer consists of an optional '-' or '+' followed by
123        // one or more digit characters appropriate to the given base,
124        // and no other characters.
125        int charCount = s.length();
126        int i = 0;
127        if (charCount > 0) {
128            char ch = s.charAt(0);
129            if (ch == '+') {
130                // Java supports leading +, but OpenSSL doesn't, so we need to strip it.
131                s = s.substring(1);
132                --charCount;
133            } else if (ch == '-') {
134                ++i;
135            }
136        }
137        if (charCount - i == 0) {
138            throw invalidBigInteger(s);
139        }
140        boolean nonAscii = false;
141        for (; i < charCount; ++i) {
142            char ch = s.charAt(i);
143            if (Character.digit(ch, base) == -1) {
144                throw invalidBigInteger(s);
145            }
146            if (ch > 128) {
147                nonAscii = true;
148            }
149        }
150        return nonAscii ? toAscii(s, base) : s;
151    }
152
153    // Java supports non-ASCII decimal digits, but OpenSSL doesn't.
154    // We need to translate the decimal digits but leave any other characters alone.
155    // This method assumes it's being called on a string that has already been validated.
156    private static String toAscii(String s, int base) {
157        int length = s.length();
158        StringBuilder result = new StringBuilder(length);
159        for (int i = 0; i < length; ++i) {
160            char ch = s.charAt(i);
161            int value = Character.digit(ch, base);
162            if (value >= 0 && value <= 9) {
163                ch = (char) ('0' + value);
164            }
165            result.append(ch);
166        }
167        return result.toString();
168    }
169
170    void putBigEndian(byte[] a, boolean neg) {
171        this.makeValid();
172        NativeBN.BN_bin2bn(a, a.length, neg, this.bignum);
173    }
174
175    void putLittleEndianInts(int[] a, boolean neg) {
176        this.makeValid();
177        NativeBN.litEndInts2bn(a, a.length, neg, this.bignum);
178    }
179
180    void putBigEndianTwosComplement(byte[] a) {
181        this.makeValid();
182        NativeBN.twosComp2bn(a, a.length, this.bignum);
183    }
184
185
186    long longInt() {
187        return NativeBN.longInt(this.bignum);
188    }
189
190    String decString() {
191        return NativeBN.BN_bn2dec(this.bignum);
192    }
193
194    String hexString() {
195        return NativeBN.BN_bn2hex(this.bignum);
196    }
197
198    byte[] bigEndianMagnitude() {
199        return NativeBN.BN_bn2bin(this.bignum);
200    }
201
202    int[] littleEndianIntsMagnitude() {
203        return NativeBN.bn2litEndInts(this.bignum);
204    }
205
206    int sign() {
207        return NativeBN.sign(this.bignum);
208    }
209
210    void setSign(int val) {
211        if (val > 0) {
212            NativeBN.BN_set_negative(this.bignum, 0);
213        } else {
214            if (val < 0) NativeBN.BN_set_negative(this.bignum, 1);
215        }
216    }
217
218    boolean twosCompFitsIntoBytes(int desiredByteCount) {
219        int actualByteCount = (NativeBN.bitLength(this.bignum) + 7) / 8;
220        return actualByteCount <= desiredByteCount;
221    }
222
223    int bitLength() {
224        return NativeBN.bitLength(this.bignum);
225    }
226
227    boolean isBitSet(int n) {
228        return NativeBN.BN_is_bit_set(this.bignum, n);
229    }
230
231    // n > 0: shift left (multiply)
232    static BigInt shift(BigInt a, int n) {
233        BigInt r = newBigInt();
234        NativeBN.BN_shift(r.bignum, a.bignum, n);
235        return r;
236    }
237
238    void shift(int n) {
239        NativeBN.BN_shift(this.bignum, this.bignum, n);
240    }
241
242    void addPositiveInt(int w) {
243        NativeBN.BN_add_word(this.bignum, w);
244    }
245
246    void multiplyByPositiveInt(int w) {
247        NativeBN.BN_mul_word(this.bignum, w);
248    }
249
250    static int remainderByPositiveInt(BigInt a, int w) {
251        return NativeBN.BN_mod_word(a.bignum, w);
252    }
253
254    static BigInt addition(BigInt a, BigInt b) {
255        BigInt r = newBigInt();
256        NativeBN.BN_add(r.bignum, a.bignum, b.bignum);
257        return r;
258    }
259
260    void add(BigInt a) {
261        NativeBN.BN_add(this.bignum, this.bignum, a.bignum);
262    }
263
264    static BigInt subtraction(BigInt a, BigInt b) {
265        BigInt r = newBigInt();
266        NativeBN.BN_sub(r.bignum, a.bignum, b.bignum);
267        return r;
268    }
269
270
271    static BigInt gcd(BigInt a, BigInt b) {
272        BigInt r = newBigInt();
273        NativeBN.BN_gcd(r.bignum, a.bignum, b.bignum);
274        return r;
275    }
276
277    static BigInt product(BigInt a, BigInt b) {
278        BigInt r = newBigInt();
279        NativeBN.BN_mul(r.bignum, a.bignum, b.bignum);
280        return r;
281    }
282
283    static BigInt bigExp(BigInt a, BigInt p) {
284        // Sign of p is ignored!
285        BigInt r = newBigInt();
286        NativeBN.BN_exp(r.bignum, a.bignum, p.bignum);
287        return r;
288    }
289
290    static BigInt exp(BigInt a, int p) {
291        // Sign of p is ignored!
292        BigInt power = new BigInt();
293        power.putLongInt(p);
294        return bigExp(a, power);
295        // OPTIONAL:
296        // int BN_sqr(BigInteger r, BigInteger a, BN_CTX ctx);
297        // int BN_sqr(BIGNUM *r, const BIGNUM *a,BN_CTX *ctx);
298    }
299
300    static void division(BigInt dividend, BigInt divisor, BigInt quotient, BigInt remainder) {
301        long quot, rem;
302        if (quotient != null) {
303            quotient.makeValid();
304            quot = quotient.bignum;
305        } else {
306            quot = 0;
307        }
308        if (remainder != null) {
309            remainder.makeValid();
310            rem = remainder.bignum;
311        } else {
312            rem = 0;
313        }
314        NativeBN.BN_div(quot, rem, dividend.bignum, divisor.bignum);
315    }
316
317    static BigInt modulus(BigInt a, BigInt m) {
318        // Sign of p is ignored! ?
319        BigInt r = newBigInt();
320        NativeBN.BN_nnmod(r.bignum, a.bignum, m.bignum);
321        return r;
322    }
323
324    static BigInt modExp(BigInt a, BigInt p, BigInt m) {
325        // Sign of p is ignored!
326        BigInt r = newBigInt();
327        NativeBN.BN_mod_exp(r.bignum, a.bignum, p.bignum, m.bignum);
328        return r;
329    }
330
331
332    static BigInt modInverse(BigInt a, BigInt m) {
333        BigInt r = newBigInt();
334        NativeBN.BN_mod_inverse(r.bignum, a.bignum, m.bignum);
335        return r;
336    }
337
338
339    static BigInt generatePrimeDefault(int bitLength) {
340        BigInt r = newBigInt();
341        NativeBN.BN_generate_prime_ex(r.bignum, bitLength, false, 0, 0, 0);
342        return r;
343    }
344
345    boolean isPrime(int certainty) {
346        return NativeBN.BN_is_prime_ex(bignum, certainty, 0);
347    }
348}
349