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