diff options
Diffstat (limited to 'luni/src')
18 files changed, 248 insertions, 7599 deletions
diff --git a/luni/src/main/java/java/math/BigDecimal.java b/luni/src/main/java/java/math/BigDecimal.java deleted file mode 100644 index 6ba251b8b7..0000000000 --- a/luni/src/main/java/java/math/BigDecimal.java +++ /dev/null @@ -1,2973 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package java.math; - -import java.io.IOException; -import java.io.ObjectInputStream; -import java.io.ObjectOutputStream; -import java.io.Serializable; -import java.util.Arrays; -import libcore.math.MathUtils; - -/** - * An immutable arbitrary-precision signed decimal. - * - * <p>A value is represented by an arbitrary-precision "unscaled value" and a signed 32-bit "scale", - * combined thus: {@code unscaled * 10<sup>-scale</sup>}. See {@link #unscaledValue} and {@link #scale}. - * - * <p>Most operations allow you to supply a {@link MathContext} to specify a desired rounding mode. - */ -public class BigDecimal extends Number implements Comparable<BigDecimal>, Serializable { - - /** - * Rounding mode where positive values are rounded towards positive infinity - * and negative values towards negative infinity. - * - * @see RoundingMode#UP - */ - public static final int ROUND_UP = 0; - - /** - * Rounding mode where the values are rounded towards zero. - * - * @see RoundingMode#DOWN - */ - public static final int ROUND_DOWN = 1; - - /** - * Rounding mode to round towards positive infinity. For positive values - * this rounding mode behaves as {@link #ROUND_UP}, for negative values as - * {@link #ROUND_DOWN}. - * - * @see RoundingMode#CEILING - */ - public static final int ROUND_CEILING = 2; - - /** - * Rounding mode to round towards negative infinity. For positive values - * this rounding mode behaves as {@link #ROUND_DOWN}, for negative values as - * {@link #ROUND_UP}. - * - * @see RoundingMode#FLOOR - */ - public static final int ROUND_FLOOR = 3; - - /** - * Rounding mode where values are rounded towards the nearest neighbor. - * Ties are broken by rounding up. - * - * @see RoundingMode#HALF_UP - */ - public static final int ROUND_HALF_UP = 4; - - /** - * Rounding mode where values are rounded towards the nearest neighbor. - * Ties are broken by rounding down. - * - * @see RoundingMode#HALF_DOWN - */ - public static final int ROUND_HALF_DOWN = 5; - - /** - * Rounding mode where values are rounded towards the nearest neighbor. - * Ties are broken by rounding to the even neighbor. - * - * @see RoundingMode#HALF_EVEN - */ - public static final int ROUND_HALF_EVEN = 6; - - /** - * Rounding mode where the rounding operations throws an {@code - * ArithmeticException} for the case that rounding is necessary, i.e. for - * the case that the value cannot be represented exactly. - * - * @see RoundingMode#UNNECESSARY - */ - public static final int ROUND_UNNECESSARY = 7; - - /** This is the serialVersionUID used by the sun implementation. */ - private static final long serialVersionUID = 6108874887143696463L; - - /** The double closest to {@code Log10(2)}. */ - private static final double LOG10_2 = 0.3010299956639812; - - /** The <code>String</code> representation is cached. */ - private transient String toStringImage = null; - - /** Cache for the hash code. */ - private transient int hashCode = 0; - - /** - * An array with powers of five that fit in the type <code>long</code> - * (<code>5^0,5^1,...,5^27</code>). - */ - private static final BigInteger[] FIVE_POW; - - /** - * An array with powers of ten that fit in the type <code>long</code> - * (<code>10^0,10^1,...,10^18</code>). - */ - private static final BigInteger[] TEN_POW; - - private static final long[] LONG_FIVE_POW = new long[] - { 1L, - 5L, - 25L, - 125L, - 625L, - 3125L, - 15625L, - 78125L, - 390625L, - 1953125L, - 9765625L, - 48828125L, - 244140625L, - 1220703125L, - 6103515625L, - 30517578125L, - 152587890625L, - 762939453125L, - 3814697265625L, - 19073486328125L, - 95367431640625L, - 476837158203125L, - 2384185791015625L, - 11920928955078125L, - 59604644775390625L, - 298023223876953125L, - 1490116119384765625L, - 7450580596923828125L, }; - - private static final int[] LONG_FIVE_POW_BIT_LENGTH = new int[LONG_FIVE_POW.length]; - private static final int[] LONG_POWERS_OF_TEN_BIT_LENGTH = new int[MathUtils.LONG_POWERS_OF_TEN.length]; - - private static final int BI_SCALED_BY_ZERO_LENGTH = 11; - - /** - * An array with the first <code>BigInteger</code> scaled by zero. - * (<code>[0,0],[1,0],...,[10,0]</code>). - */ - private static final BigDecimal[] BI_SCALED_BY_ZERO = new BigDecimal[BI_SCALED_BY_ZERO_LENGTH]; - - /** - * An array with the zero number scaled by the first positive scales. - * (<code>0*10^0, 0*10^1, ..., 0*10^10</code>). - */ - private static final BigDecimal[] ZERO_SCALED_BY = new BigDecimal[11]; - - /** An array filled with characters <code>'0'</code>. */ - private static final char[] CH_ZEROS = new char[100]; - - static { - Arrays.fill(CH_ZEROS, '0'); - - for (int i = 0; i < ZERO_SCALED_BY.length; ++i) { - BI_SCALED_BY_ZERO[i] = new BigDecimal(i, 0); - ZERO_SCALED_BY[i] = new BigDecimal(0, i); - } - for (int i = 0; i < LONG_FIVE_POW_BIT_LENGTH.length; ++i) { - LONG_FIVE_POW_BIT_LENGTH[i] = bitLength(LONG_FIVE_POW[i]); - } - for (int i = 0; i < LONG_POWERS_OF_TEN_BIT_LENGTH.length; ++i) { - LONG_POWERS_OF_TEN_BIT_LENGTH[i] = bitLength(MathUtils.LONG_POWERS_OF_TEN[i]); - } - - // Taking the references of useful powers. - TEN_POW = Multiplication.bigTenPows; - FIVE_POW = Multiplication.bigFivePows; - } - - /** - * The constant zero as a {@code BigDecimal}. - */ - public static final BigDecimal ZERO = new BigDecimal(0, 0); - - /** - * The constant one as a {@code BigDecimal}. - */ - public static final BigDecimal ONE = new BigDecimal(1, 0); - - /** - * The constant ten as a {@code BigDecimal}. - */ - public static final BigDecimal TEN = new BigDecimal(10, 0); - - /** - * The arbitrary precision integer (unscaled value) in the internal - * representation of {@code BigDecimal}. - */ - private BigInteger intVal; - - private transient int bitLength; - - private transient long smallValue; - - /** - * The 32-bit integer scale in the internal representation of {@code BigDecimal}. - */ - private int scale; - - /** - * Represent the number of decimal digits in the unscaled value. This - * precision is calculated the first time, and used in the following calls - * of method <code>precision()</code>. Note that some call to the private - * method <code>inplaceRound()</code> could update this field. - * - * @see #precision() - * @see #inplaceRound(MathContext) - */ - private transient int precision = 0; - - private BigDecimal(long smallValue, int scale){ - this.smallValue = smallValue; - this.scale = scale; - this.bitLength = bitLength(smallValue); - } - - private BigDecimal(int smallValue, int scale){ - this.smallValue = smallValue; - this.scale = scale; - this.bitLength = bitLength(smallValue); - } - - /** - * Constructs a new {@code BigDecimal} instance from a string representation - * given as a character array. - * - * @param in - * array of characters containing the string representation of - * this {@code BigDecimal}. - * @param offset - * first index to be copied. - * @param len - * number of characters to be used. - * @throws NumberFormatException - * if {@code offset < 0 || len <= 0 || offset+len-1 < 0 || - * offset+len-1 >= in.length}, or if {@code in} does not - * contain a valid string representation of a big decimal. - */ - public BigDecimal(char[] in, int offset, int len) { - int begin = offset; // first index to be copied - int last = offset + (len - 1); // last index to be copied - String scaleString; // buffer for scale - StringBuilder unscaledBuffer; // buffer for unscaled value - long newScale; // the new scale - - if (in == null) { - throw new NullPointerException("in == null"); - } - if ((last >= in.length) || (offset < 0) || (len <= 0) || (last < 0)) { - throw new NumberFormatException("Bad offset/length: offset=" + offset + - " len=" + len + " in.length=" + in.length); - } - unscaledBuffer = new StringBuilder(len); - int bufLength = 0; - // To skip a possible '+' symbol - if ((offset <= last) && (in[offset] == '+')) { - offset++; - begin++; - } - int counter = 0; - boolean wasNonZero = false; - // Accumulating all digits until a possible decimal point - for (; (offset <= last) && (in[offset] != '.') && (in[offset] != 'e') && (in[offset] != 'E'); offset++) { - if (!wasNonZero) { - if (in[offset] == '0') { - counter++; - } else { - wasNonZero = true; - } - } - - } - unscaledBuffer.append(in, begin, offset - begin); - bufLength += offset - begin; - // A decimal point was found - if ((offset <= last) && (in[offset] == '.')) { - offset++; - // Accumulating all digits until a possible exponent - begin = offset; - for (; (offset <= last) && (in[offset] != 'e') - && (in[offset] != 'E'); offset++) { - if (!wasNonZero) { - if (in[offset] == '0') { - counter++; - } else { - wasNonZero = true; - } - } - } - scale = offset - begin; - bufLength +=scale; - unscaledBuffer.append(in, begin, scale); - } else { - scale = 0; - } - // An exponent was found - if ((offset <= last) && ((in[offset] == 'e') || (in[offset] == 'E'))) { - offset++; - // Checking for a possible sign of scale - begin = offset; - if ((offset <= last) && (in[offset] == '+')) { - offset++; - if ((offset <= last) && (in[offset] != '-')) { - begin++; - } - } - // Accumulating all remaining digits - scaleString = String.valueOf(in, begin, last + 1 - begin); - // Checking if the scale is defined - newScale = (long)scale - Integer.parseInt(scaleString); - scale = (int)newScale; - if (newScale != scale) { - throw new NumberFormatException("Scale out of range"); - } - } - // Parsing the unscaled value - if (bufLength < 19) { - smallValue = Long.parseLong(unscaledBuffer.toString()); - bitLength = bitLength(smallValue); - } else { - setUnscaledValue(new BigInteger(unscaledBuffer.toString())); - } - } - - /** - * Constructs a new {@code BigDecimal} instance from a string representation - * given as a character array. - * - * @param in - * array of characters containing the string representation of - * this {@code BigDecimal}. - * @param offset - * first index to be copied. - * @param len - * number of characters to be used. - * @param mc - * rounding mode and precision for the result of this operation. - * @throws NumberFormatException - * if {@code offset < 0 || len <= 0 || offset+len-1 < 0 || - * offset+len-1 >= in.length}, or if {@code in} does not - * contain a valid string representation of a big decimal. - * @throws ArithmeticException - * if {@code mc.precision > 0} and {@code mc.roundingMode == - * UNNECESSARY} and the new big decimal cannot be represented - * within the given precision without rounding. - */ - public BigDecimal(char[] in, int offset, int len, MathContext mc) { - this(in, offset, len); - inplaceRound(mc); - } - - /** - * Constructs a new {@code BigDecimal} instance from a string representation - * given as a character array. - * - * @param in - * array of characters containing the string representation of - * this {@code BigDecimal}. - * @throws NumberFormatException - * if {@code in} does not contain a valid string representation - * of a big decimal. - */ - public BigDecimal(char[] in) { - this(in, 0, in.length); - } - - /** - * Constructs a new {@code BigDecimal} instance from a string representation - * given as a character array. The result is rounded according to the - * specified math context. - * - * @param in - * array of characters containing the string representation of - * this {@code BigDecimal}. - * @param mc - * rounding mode and precision for the result of this operation. - * @throws NumberFormatException - * if {@code in} does not contain a valid string representation - * of a big decimal. - * @throws ArithmeticException - * if {@code mc.precision > 0} and {@code mc.roundingMode == - * UNNECESSARY} and the new big decimal cannot be represented - * within the given precision without rounding. - */ - public BigDecimal(char[] in, MathContext mc) { - this(in, 0, in.length); - inplaceRound(mc); - } - - /** - * Constructs a new {@code BigDecimal} instance from a string - * representation. - * - * @throws NumberFormatException - * if {@code val} does not contain a valid string representation - * of a big decimal. - */ - public BigDecimal(String val) { - this(val.toCharArray(), 0, val.length()); - } - - /** - * Constructs a new {@code BigDecimal} instance from a string - * representation. The result is rounded according to the specified math - * context. - * - * @param mc - * rounding mode and precision for the result of this operation. - * @throws NumberFormatException - * if {@code val} does not contain a valid string representation - * of a big decimal. - * @throws ArithmeticException - * if {@code mc.precision > 0} and {@code mc.roundingMode == - * UNNECESSARY} and the new big decimal cannot be represented - * within the given precision without rounding. - */ - public BigDecimal(String val, MathContext mc) { - this(val.toCharArray(), 0, val.length()); - inplaceRound(mc); - } - - /** - * Constructs a new {@code BigDecimal} instance from the 64bit double - * {@code val}. The constructed big decimal is equivalent to the given - * double. For example, {@code new BigDecimal(0.1)} is equal to {@code - * 0.1000000000000000055511151231257827021181583404541015625}. This happens - * as {@code 0.1} cannot be represented exactly in binary. - * <p> - * To generate a big decimal instance which is equivalent to {@code 0.1} use - * the {@code BigDecimal(String)} constructor. - * - * @param val - * double value to be converted to a {@code BigDecimal} instance. - * @throws NumberFormatException - * if {@code val} is infinity or not a number. - */ - public BigDecimal(double val) { - if (Double.isInfinite(val) || Double.isNaN(val)) { - throw new NumberFormatException("Infinity or NaN: " + val); - } - long bits = Double.doubleToLongBits(val); // IEEE-754 - long mantissa; - int trailingZeros; - // Extracting the exponent, note that the bias is 1023 - scale = 1075 - (int)((bits >> 52) & 0x7FFL); - // Extracting the 52 bits of the mantissa. - mantissa = (scale == 1075) ? (bits & 0xFFFFFFFFFFFFFL) << 1 - : (bits & 0xFFFFFFFFFFFFFL) | 0x10000000000000L; - if (mantissa == 0) { - scale = 0; - precision = 1; - } - // To simplify all factors '2' in the mantissa - if (scale > 0) { - trailingZeros = Math.min(scale, Long.numberOfTrailingZeros(mantissa)); - mantissa >>>= trailingZeros; - scale -= trailingZeros; - } - // Calculating the new unscaled value and the new scale - if((bits >> 63) != 0) { - mantissa = -mantissa; - } - int mantissaBits = bitLength(mantissa); - if (scale < 0) { - bitLength = mantissaBits == 0 ? 0 : mantissaBits - scale; - if(bitLength < 64) { - smallValue = mantissa << (-scale); - } else { - BigInt bi = new BigInt(); - bi.putLongInt(mantissa); - bi.shift(-scale); - intVal = new BigInteger(bi); - } - scale = 0; - } else if (scale > 0) { - // m * 2^e = (m * 5^(-e)) * 10^e - if(scale < LONG_FIVE_POW.length - && mantissaBits+LONG_FIVE_POW_BIT_LENGTH[scale] < 64) { - smallValue = mantissa * LONG_FIVE_POW[scale]; - bitLength = bitLength(smallValue); - } else { - setUnscaledValue(Multiplication.multiplyByFivePow(BigInteger.valueOf(mantissa), scale)); - } - } else { // scale == 0 - smallValue = mantissa; - bitLength = mantissaBits; - } - } - - /** - * Constructs a new {@code BigDecimal} instance from the 64bit double - * {@code val}. The constructed big decimal is equivalent to the given - * double. For example, {@code new BigDecimal(0.1)} is equal to {@code - * 0.1000000000000000055511151231257827021181583404541015625}. This happens - * as {@code 0.1} cannot be represented exactly in binary. - * <p> - * To generate a big decimal instance which is equivalent to {@code 0.1} use - * the {@code BigDecimal(String)} constructor. - * - * @param val - * double value to be converted to a {@code BigDecimal} instance. - * @param mc - * rounding mode and precision for the result of this operation. - * @throws NumberFormatException - * if {@code val} is infinity or not a number. - * @throws ArithmeticException - * if {@code mc.precision > 0} and {@code mc.roundingMode == - * UNNECESSARY} and the new big decimal cannot be represented - * within the given precision without rounding. - */ - public BigDecimal(double val, MathContext mc) { - this(val); - inplaceRound(mc); - } - - /** - * Constructs a new {@code BigDecimal} instance from the given big integer - * {@code val}. The scale of the result is {@code 0}. - */ - public BigDecimal(BigInteger val) { - this(val, 0); - } - - /** - * Constructs a new {@code BigDecimal} instance from the given big integer - * {@code val}. The scale of the result is {@code 0}. - * - * @param mc - * rounding mode and precision for the result of this operation. - * @throws ArithmeticException - * if {@code mc.precision > 0} and {@code mc.roundingMode == - * UNNECESSARY} and the new big decimal cannot be represented - * within the given precision without rounding. - */ - public BigDecimal(BigInteger val, MathContext mc) { - this(val); - inplaceRound(mc); - } - - /** - * Constructs a new {@code BigDecimal} instance from a given unscaled value - * {@code unscaledVal} and a given scale. The value of this instance is - * {@code unscaledVal * 10<sup>-scale</sup>}). - * - * @throws NullPointerException - * if {@code unscaledVal == null}. - */ - public BigDecimal(BigInteger unscaledVal, int scale) { - if (unscaledVal == null) { - throw new NullPointerException("unscaledVal == null"); - } - this.scale = scale; - setUnscaledValue(unscaledVal); - } - - /** - * Constructs a new {@code BigDecimal} instance from a given unscaled value - * {@code unscaledVal} and a given scale. The value of this instance is - * {@code unscaledVal * 10<sup>-scale</sup>). The result is rounded according - * to the specified math context. - * - * @param mc - * rounding mode and precision for the result of this operation. - * @throws ArithmeticException - * if {@code mc.precision > 0} and {@code mc.roundingMode == - * UNNECESSARY} and the new big decimal cannot be represented - * within the given precision without rounding. - * @throws NullPointerException - * if {@code unscaledVal == null}. - */ - public BigDecimal(BigInteger unscaledVal, int scale, MathContext mc) { - this(unscaledVal, scale); - inplaceRound(mc); - } - - /** - * Constructs a new {@code BigDecimal} instance from the given int - * {@code val}. The scale of the result is 0. - * - * @param val - * int value to be converted to a {@code BigDecimal} instance. - */ - public BigDecimal(int val) { - this(val,0); - } - - /** - * Constructs a new {@code BigDecimal} instance from the given int {@code - * val}. The scale of the result is {@code 0}. The result is rounded - * according to the specified math context. - * - * @param val - * int value to be converted to a {@code BigDecimal} instance. - * @param mc - * rounding mode and precision for the result of this operation. - * @throws ArithmeticException - * if {@code mc.precision > 0} and {@code c.roundingMode == - * UNNECESSARY} and the new big decimal cannot be represented - * within the given precision without rounding. - */ - public BigDecimal(int val, MathContext mc) { - this(val,0); - inplaceRound(mc); - } - - /** - * Constructs a new {@code BigDecimal} instance from the given long {@code - * val}. The scale of the result is {@code 0}. - * - * @param val - * long value to be converted to a {@code BigDecimal} instance. - */ - public BigDecimal(long val) { - this(val,0); - } - - /** - * Constructs a new {@code BigDecimal} instance from the given long {@code - * val}. The scale of the result is {@code 0}. The result is rounded - * according to the specified math context. - * - * @param val - * long value to be converted to a {@code BigDecimal} instance. - * @param mc - * rounding mode and precision for the result of this operation. - * @throws ArithmeticException - * if {@code mc.precision > 0} and {@code mc.roundingMode == - * UNNECESSARY} and the new big decimal cannot be represented - * within the given precision without rounding. - */ - public BigDecimal(long val, MathContext mc) { - this(val); - inplaceRound(mc); - } - - /* Public Methods */ - - /** - * Returns a new {@code BigDecimal} instance whose value is equal to {@code - * unscaledVal * 10<sup>-scale</sup>}). The scale of the result is {@code - * scale}, and its unscaled value is {@code unscaledVal}. - */ - public static BigDecimal valueOf(long unscaledVal, int scale) { - if (scale == 0) { - return valueOf(unscaledVal); - } - if ((unscaledVal == 0) && (scale >= 0) - && (scale < ZERO_SCALED_BY.length)) { - return ZERO_SCALED_BY[scale]; - } - return new BigDecimal(unscaledVal, scale); - } - - /** - * Returns a new {@code BigDecimal} instance whose value is equal to {@code - * unscaledVal}. The scale of the result is {@code 0}, and its unscaled - * value is {@code unscaledVal}. - * - * @param unscaledVal - * value to be converted to a {@code BigDecimal}. - * @return {@code BigDecimal} instance with the value {@code unscaledVal}. - */ - public static BigDecimal valueOf(long unscaledVal) { - if ((unscaledVal >= 0) && (unscaledVal < BI_SCALED_BY_ZERO_LENGTH)) { - return BI_SCALED_BY_ZERO[(int)unscaledVal]; - } - return new BigDecimal(unscaledVal,0); - } - - /** - * Returns a new {@code BigDecimal} instance whose value is equal to {@code - * val}. The new decimal is constructed as if the {@code BigDecimal(String)} - * constructor is called with an argument which is equal to {@code - * Double.toString(val)}. For example, {@code valueOf("0.1")} is converted to - * (unscaled=1, scale=1), although the double {@code 0.1} cannot be - * represented exactly as a double value. In contrast to that, a new {@code - * BigDecimal(0.1)} instance has the value {@code - * 0.1000000000000000055511151231257827021181583404541015625} with an - * unscaled value {@code 1000000000000000055511151231257827021181583404541015625} - * and the scale {@code 55}. - * - * @param val - * double value to be converted to a {@code BigDecimal}. - * @return {@code BigDecimal} instance with the value {@code val}. - * @throws NumberFormatException - * if {@code val} is infinite or {@code val} is not a number - */ - public static BigDecimal valueOf(double val) { - if (Double.isInfinite(val) || Double.isNaN(val)) { - throw new NumberFormatException("Infinity or NaN: " + val); - } - return new BigDecimal(Double.toString(val)); - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this + augend}. - * The scale of the result is the maximum of the scales of the two - * arguments. - * - * @param augend - * value to be added to {@code this}. - * @return {@code this + augend}. - * @throws NullPointerException - * if {@code augend == null}. - */ - public BigDecimal add(BigDecimal augend) { - int diffScale = this.scale - augend.scale; - // Fast return when some operand is zero - if (this.isZero()) { - if (diffScale <= 0) { - return augend; - } - if (augend.isZero()) { - return this; - } - } else if (augend.isZero()) { - if (diffScale >= 0) { - return this; - } - } - // Let be: this = [u1,s1] and augend = [u2,s2] - if (diffScale == 0) { - // case s1 == s2: [u1 + u2 , s1] - if (Math.max(this.bitLength, augend.bitLength) + 1 < 64) { - return valueOf(this.smallValue + augend.smallValue, this.scale); - } - return new BigDecimal(this.getUnscaledValue().add(augend.getUnscaledValue()), this.scale); - } else if (diffScale > 0) { - // case s1 > s2 : [(u1 + u2) * 10 ^ (s1 - s2) , s1] - return addAndMult10(this, augend, diffScale); - } else {// case s2 > s1 : [(u2 + u1) * 10 ^ (s2 - s1) , s2] - return addAndMult10(augend, this, -diffScale); - } - } - - private static BigDecimal addAndMult10(BigDecimal thisValue,BigDecimal augend, int diffScale) { - if(diffScale < MathUtils.LONG_POWERS_OF_TEN.length && - Math.max(thisValue.bitLength,augend.bitLength+LONG_POWERS_OF_TEN_BIT_LENGTH[diffScale])+1<64) { - return valueOf(thisValue.smallValue+augend.smallValue*MathUtils.LONG_POWERS_OF_TEN[diffScale],thisValue.scale); - } else { - BigInt bi = Multiplication.multiplyByTenPow(augend.getUnscaledValue(),diffScale).getBigInt(); - bi.add(thisValue.getUnscaledValue().getBigInt()); - return new BigDecimal(new BigInteger(bi), thisValue.scale); - } - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this + augend}. - * The result is rounded according to the passed context {@code mc}. - * - * @param augend - * value to be added to {@code this}. - * @param mc - * rounding mode and precision for the result of this operation. - * @return {@code this + augend}. - * @throws NullPointerException - * if {@code augend == null} or {@code mc == null}. - */ - public BigDecimal add(BigDecimal augend, MathContext mc) { - BigDecimal larger; // operand with the largest unscaled value - BigDecimal smaller; // operand with the smallest unscaled value - BigInteger tempBI; - long diffScale = (long)this.scale - augend.scale; - int largerSignum; - // Some operand is zero or the precision is infinity - if ((augend.isZero()) || (this.isZero()) - || (mc.getPrecision() == 0)) { - return add(augend).round(mc); - } - // Cases where there is room for optimizations - if (this.approxPrecision() < diffScale - 1) { - larger = augend; - smaller = this; - } else if (augend.approxPrecision() < -diffScale - 1) { - larger = this; - smaller = augend; - } else {// No optimization is done - return add(augend).round(mc); - } - if (mc.getPrecision() >= larger.approxPrecision()) { - // No optimization is done - return add(augend).round(mc); - } - // Cases where it's unnecessary to add two numbers with very different scales - largerSignum = larger.signum(); - if (largerSignum == smaller.signum()) { - tempBI = Multiplication.multiplyByPositiveInt(larger.getUnscaledValue(),10) - .add(BigInteger.valueOf(largerSignum)); - } else { - tempBI = larger.getUnscaledValue().subtract( - BigInteger.valueOf(largerSignum)); - tempBI = Multiplication.multiplyByPositiveInt(tempBI,10) - .add(BigInteger.valueOf(largerSignum * 9)); - } - // Rounding the improved adding - larger = new BigDecimal(tempBI, larger.scale + 1); - return larger.round(mc); - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this - subtrahend}. - * The scale of the result is the maximum of the scales of the two arguments. - * - * @param subtrahend - * value to be subtracted from {@code this}. - * @return {@code this - subtrahend}. - * @throws NullPointerException - * if {@code subtrahend == null}. - */ - public BigDecimal subtract(BigDecimal subtrahend) { - int diffScale = this.scale - subtrahend.scale; - // Fast return when some operand is zero - if (this.isZero()) { - if (diffScale <= 0) { - return subtrahend.negate(); - } - if (subtrahend.isZero()) { - return this; - } - } else if (subtrahend.isZero()) { - if (diffScale >= 0) { - return this; - } - } - // Let be: this = [u1,s1] and subtrahend = [u2,s2] so: - if (diffScale == 0) { - // case s1 = s2 : [u1 - u2 , s1] - if (Math.max(this.bitLength, subtrahend.bitLength) + 1 < 64) { - return valueOf(this.smallValue - subtrahend.smallValue,this.scale); - } - return new BigDecimal(this.getUnscaledValue().subtract(subtrahend.getUnscaledValue()), this.scale); - } else if (diffScale > 0) { - // case s1 > s2 : [ u1 - u2 * 10 ^ (s1 - s2) , s1 ] - if(diffScale < MathUtils.LONG_POWERS_OF_TEN.length && - Math.max(this.bitLength,subtrahend.bitLength+LONG_POWERS_OF_TEN_BIT_LENGTH[diffScale])+1<64) { - return valueOf(this.smallValue-subtrahend.smallValue*MathUtils.LONG_POWERS_OF_TEN[diffScale],this.scale); - } - return new BigDecimal(this.getUnscaledValue().subtract( - Multiplication.multiplyByTenPow(subtrahend.getUnscaledValue(),diffScale)), this.scale); - } else {// case s2 > s1 : [ u1 * 10 ^ (s2 - s1) - u2 , s2 ] - diffScale = -diffScale; - if(diffScale < MathUtils.LONG_POWERS_OF_TEN.length && - Math.max(this.bitLength+LONG_POWERS_OF_TEN_BIT_LENGTH[diffScale],subtrahend.bitLength)+1<64) { - return valueOf(this.smallValue*MathUtils.LONG_POWERS_OF_TEN[diffScale]-subtrahend.smallValue,subtrahend.scale); - } - return new BigDecimal(Multiplication.multiplyByTenPow(this.getUnscaledValue(),diffScale) - .subtract(subtrahend.getUnscaledValue()), subtrahend.scale); - } - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this - subtrahend}. - * The result is rounded according to the passed context {@code mc}. - * - * @param subtrahend - * value to be subtracted from {@code this}. - * @param mc - * rounding mode and precision for the result of this operation. - * @return {@code this - subtrahend}. - * @throws NullPointerException - * if {@code subtrahend == null} or {@code mc == null}. - */ - public BigDecimal subtract(BigDecimal subtrahend, MathContext mc) { - long diffScale = subtrahend.scale - (long)this.scale; - int thisSignum; - BigDecimal leftOperand; // it will be only the left operand (this) - BigInteger tempBI; - // Some operand is zero or the precision is infinity - if ((subtrahend.isZero()) || (this.isZero()) - || (mc.getPrecision() == 0)) { - return subtract(subtrahend).round(mc); - } - // Now: this != 0 and subtrahend != 0 - if (subtrahend.approxPrecision() < diffScale - 1) { - // Cases where it is unnecessary to subtract two numbers with very different scales - if (mc.getPrecision() < this.approxPrecision()) { - thisSignum = this.signum(); - if (thisSignum != subtrahend.signum()) { - tempBI = Multiplication.multiplyByPositiveInt(this.getUnscaledValue(), 10) - .add(BigInteger.valueOf(thisSignum)); - } else { - tempBI = this.getUnscaledValue().subtract(BigInteger.valueOf(thisSignum)); - tempBI = Multiplication.multiplyByPositiveInt(tempBI, 10) - .add(BigInteger.valueOf(thisSignum * 9)); - } - // Rounding the improved subtracting - leftOperand = new BigDecimal(tempBI, this.scale + 1); - return leftOperand.round(mc); - } - } - // No optimization is done - return subtract(subtrahend).round(mc); - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this * - * multiplicand}. The scale of the result is the sum of the scales of the - * two arguments. - * - * @param multiplicand - * value to be multiplied with {@code this}. - * @return {@code this * multiplicand}. - * @throws NullPointerException - * if {@code multiplicand == null}. - */ - public BigDecimal multiply(BigDecimal multiplicand) { - long newScale = (long)this.scale + multiplicand.scale; - - if ((this.isZero()) || (multiplicand.isZero())) { - return zeroScaledBy(newScale); - } - /* Let be: this = [u1,s1] and multiplicand = [u2,s2] so: - * this x multiplicand = [ s1 * s2 , s1 + s2 ] */ - if (this.bitLength + multiplicand.bitLength < 64) { - long unscaledValue = this.smallValue * multiplicand.smallValue; - // b/19185440 Case where result should be +2^63 but unscaledValue overflowed to -2^63 - boolean longMultiplicationOverflowed = (unscaledValue == Long.MIN_VALUE) && - (Math.signum(smallValue) * Math.signum(multiplicand.smallValue) > 0); - if (!longMultiplicationOverflowed) { - return valueOf(unscaledValue, safeLongToInt(newScale)); - } - } - return new BigDecimal(this.getUnscaledValue().multiply( - multiplicand.getUnscaledValue()), safeLongToInt(newScale)); - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this * - * multiplicand}. The result is rounded according to the passed context - * {@code mc}. - * - * @param multiplicand - * value to be multiplied with {@code this}. - * @param mc - * rounding mode and precision for the result of this operation. - * @return {@code this * multiplicand}. - * @throws NullPointerException - * if {@code multiplicand == null} or {@code mc == null}. - */ - public BigDecimal multiply(BigDecimal multiplicand, MathContext mc) { - BigDecimal result = multiply(multiplicand); - - result.inplaceRound(mc); - return result; - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this / divisor}. - * As scale of the result the parameter {@code scale} is used. If rounding - * is required to meet the specified scale, then the specified rounding mode - * {@code roundingMode} is applied. - * - * @param divisor - * value by which {@code this} is divided. - * @param scale - * the scale of the result returned. - * @param roundingMode - * rounding mode to be used to round the result. - * @return {@code this / divisor} rounded according to the given rounding - * mode. - * @throws NullPointerException - * if {@code divisor == null}. - * @throws IllegalArgumentException - * if {@code roundingMode} is not a valid rounding mode. - * @throws ArithmeticException - * if {@code divisor == 0}. - * @throws ArithmeticException - * if {@code roundingMode == ROUND_UNNECESSARY} and rounding is - * necessary according to the given scale. - */ - public BigDecimal divide(BigDecimal divisor, int scale, int roundingMode) { - return divide(divisor, scale, RoundingMode.valueOf(roundingMode)); - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this / divisor}. - * As scale of the result the parameter {@code scale} is used. If rounding - * is required to meet the specified scale, then the specified rounding mode - * {@code roundingMode} is applied. - * - * @param divisor - * value by which {@code this} is divided. - * @param scale - * the scale of the result returned. - * @param roundingMode - * rounding mode to be used to round the result. - * @return {@code this / divisor} rounded according to the given rounding - * mode. - * @throws NullPointerException - * if {@code divisor == null} or {@code roundingMode == null}. - * @throws ArithmeticException - * if {@code divisor == 0}. - * @throws ArithmeticException - * if {@code roundingMode == RoundingMode.UNNECESSAR}Y and - * rounding is necessary according to the given scale and given - * precision. - */ - public BigDecimal divide(BigDecimal divisor, int scale, RoundingMode roundingMode) { - // Let be: this = [u1,s1] and divisor = [u2,s2] - if (roundingMode == null) { - throw new NullPointerException("roundingMode == null"); - } - if (divisor.isZero()) { - throw new ArithmeticException("Division by zero"); - } - - long diffScale = ((long)this.scale - divisor.scale) - scale; - - // Check whether the diffScale will fit into an int. See http://b/17393664. - if (bitLength(diffScale) > 32) { - throw new ArithmeticException( - "Unable to perform divisor / dividend scaling: the difference in scale is too" + - " big (" + diffScale + ")"); - } - - if(this.bitLength < 64 && divisor.bitLength < 64 ) { - if(diffScale == 0) { - // http://b/26105053 - corner case: Long.MIN_VALUE / (-1) overflows a long - if (this.smallValue != Long.MIN_VALUE || divisor.smallValue != -1) { - return dividePrimitiveLongs(this.smallValue, - divisor.smallValue, - scale, - roundingMode); - } - } else if(diffScale > 0) { - if(diffScale < MathUtils.LONG_POWERS_OF_TEN.length && - divisor.bitLength + LONG_POWERS_OF_TEN_BIT_LENGTH[(int)diffScale] < 64) { - return dividePrimitiveLongs(this.smallValue, - divisor.smallValue*MathUtils.LONG_POWERS_OF_TEN[(int)diffScale], - scale, - roundingMode); - } - } else { // diffScale < 0 - if(-diffScale < MathUtils.LONG_POWERS_OF_TEN.length && - this.bitLength + LONG_POWERS_OF_TEN_BIT_LENGTH[(int)-diffScale] < 64) { - return dividePrimitiveLongs(this.smallValue*MathUtils.LONG_POWERS_OF_TEN[(int)-diffScale], - divisor.smallValue, - scale, - roundingMode); - } - - } - } - BigInteger scaledDividend = this.getUnscaledValue(); - BigInteger scaledDivisor = divisor.getUnscaledValue(); // for scaling of 'u2' - - if (diffScale > 0) { - // Multiply 'u2' by: 10^((s1 - s2) - scale) - scaledDivisor = Multiplication.multiplyByTenPow(scaledDivisor, (int)diffScale); - } else if (diffScale < 0) { - // Multiply 'u1' by: 10^(scale - (s1 - s2)) - scaledDividend = Multiplication.multiplyByTenPow(scaledDividend, (int)-diffScale); - } - return divideBigIntegers(scaledDividend, scaledDivisor, scale, roundingMode); - } - - private static BigDecimal divideBigIntegers(BigInteger scaledDividend, BigInteger scaledDivisor, int scale, RoundingMode roundingMode) { - - BigInteger[] quotAndRem = scaledDividend.divideAndRemainder(scaledDivisor); // quotient and remainder - // If after division there is a remainder... - BigInteger quotient = quotAndRem[0]; - BigInteger remainder = quotAndRem[1]; - if (remainder.signum() == 0) { - return new BigDecimal(quotient, scale); - } - int sign = scaledDividend.signum() * scaledDivisor.signum(); - int compRem; // 'compare to remainder' - if(scaledDivisor.bitLength() < 63) { // 63 in order to avoid out of long after *2 - long rem = remainder.longValue(); - long divisor = scaledDivisor.longValue(); - compRem = compareForRounding(rem, divisor); - // To look if there is a carry - compRem = roundingBehavior(quotient.testBit(0) ? 1 : 0, - sign * (5 + compRem), roundingMode); - - } else { - // Checking if: remainder * 2 >= scaledDivisor - compRem = remainder.abs().shiftLeftOneBit().compareTo(scaledDivisor.abs()); - compRem = roundingBehavior(quotient.testBit(0) ? 1 : 0, - sign * (5 + compRem), roundingMode); - } - if (compRem != 0) { - if(quotient.bitLength() < 63) { - return valueOf(quotient.longValue() + compRem,scale); - } - quotient = quotient.add(BigInteger.valueOf(compRem)); - return new BigDecimal(quotient, scale); - } - // Constructing the result with the appropriate unscaled value - return new BigDecimal(quotient, scale); - } - - private static BigDecimal dividePrimitiveLongs(long scaledDividend, long scaledDivisor, int scale, RoundingMode roundingMode) { - long quotient = scaledDividend / scaledDivisor; - long remainder = scaledDividend % scaledDivisor; - int sign = Long.signum( scaledDividend ) * Long.signum( scaledDivisor ); - if (remainder != 0) { - // Checking if: remainder * 2 >= scaledDivisor - int compRem = compareForRounding(remainder, scaledDivisor); // 'compare to remainder' - // To look if there is a carry - quotient += roundingBehavior(((int)quotient) & 1, - sign * (5 + compRem), - roundingMode); - } - // Constructing the result with the appropriate unscaled value - return valueOf(quotient, scale); - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this / divisor}. - * The scale of the result is the scale of {@code this}. If rounding is - * required to meet the specified scale, then the specified rounding mode - * {@code roundingMode} is applied. - * - * @param divisor - * value by which {@code this} is divided. - * @param roundingMode - * rounding mode to be used to round the result. - * @return {@code this / divisor} rounded according to the given rounding - * mode. - * @throws NullPointerException - * if {@code divisor == null}. - * @throws IllegalArgumentException - * if {@code roundingMode} is not a valid rounding mode. - * @throws ArithmeticException - * if {@code divisor == 0}. - * @throws ArithmeticException - * if {@code roundingMode == ROUND_UNNECESSARY} and rounding is - * necessary according to the scale of this. - */ - public BigDecimal divide(BigDecimal divisor, int roundingMode) { - return divide(divisor, scale, RoundingMode.valueOf(roundingMode)); - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this / divisor}. - * The scale of the result is the scale of {@code this}. If rounding is - * required to meet the specified scale, then the specified rounding mode - * {@code roundingMode} is applied. - * - * @param divisor - * value by which {@code this} is divided. - * @param roundingMode - * rounding mode to be used to round the result. - * @return {@code this / divisor} rounded according to the given rounding - * mode. - * @throws NullPointerException - * if {@code divisor == null} or {@code roundingMode == null}. - * @throws ArithmeticException - * if {@code divisor == 0}. - * @throws ArithmeticException - * if {@code roundingMode == RoundingMode.UNNECESSARY} and - * rounding is necessary according to the scale of this. - */ - public BigDecimal divide(BigDecimal divisor, RoundingMode roundingMode) { - return divide(divisor, scale, roundingMode); - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this / divisor}. - * The scale of the result is the difference of the scales of {@code this} - * and {@code divisor}. If the exact result requires more digits, then the - * scale is adjusted accordingly. For example, {@code 1/128 = 0.0078125} - * which has a scale of {@code 7} and precision {@code 5}. - * - * @param divisor - * value by which {@code this} is divided. - * @return {@code this / divisor}. - * @throws NullPointerException - * if {@code divisor == null}. - * @throws ArithmeticException - * if {@code divisor == 0}. - * @throws ArithmeticException - * if the result cannot be represented exactly. - */ - public BigDecimal divide(BigDecimal divisor) { - BigInteger p = this.getUnscaledValue(); - BigInteger q = divisor.getUnscaledValue(); - BigInteger gcd; // greatest common divisor between 'p' and 'q' - BigInteger quotAndRem[]; - long diffScale = (long)scale - divisor.scale; - int newScale; // the new scale for final quotient - int k; // number of factors "2" in 'q' - int l = 0; // number of factors "5" in 'q' - int i = 1; - int lastPow = FIVE_POW.length - 1; - - if (divisor.isZero()) { - throw new ArithmeticException("Division by zero"); - } - if (p.signum() == 0) { - return zeroScaledBy(diffScale); - } - // To divide both by the GCD - gcd = p.gcd(q); - p = p.divide(gcd); - q = q.divide(gcd); - // To simplify all "2" factors of q, dividing by 2^k - k = q.getLowestSetBit(); - q = q.shiftRight(k); - // To simplify all "5" factors of q, dividing by 5^l - do { - quotAndRem = q.divideAndRemainder(FIVE_POW[i]); - if (quotAndRem[1].signum() == 0) { - l += i; - if (i < lastPow) { - i++; - } - q = quotAndRem[0]; - } else { - if (i == 1) { - break; - } - i = 1; - } - } while (true); - // If abs(q) != 1 then the quotient is periodic - if (!q.abs().equals(BigInteger.ONE)) { - throw new ArithmeticException("Non-terminating decimal expansion; no exact representable decimal result"); - } - // The sign of the is fixed and the quotient will be saved in 'p' - if (q.signum() < 0) { - p = p.negate(); - } - // Checking if the new scale is out of range - newScale = safeLongToInt(diffScale + Math.max(k, l)); - // k >= 0 and l >= 0 implies that k - l is in the 32-bit range - i = k - l; - - p = (i > 0) ? Multiplication.multiplyByFivePow(p, i) - : p.shiftLeft(-i); - return new BigDecimal(p, newScale); - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this / divisor}. - * The result is rounded according to the passed context {@code mc}. If the - * passed math context specifies precision {@code 0}, then this call is - * equivalent to {@code this.divide(divisor)}. - * - * @param divisor - * value by which {@code this} is divided. - * @param mc - * rounding mode and precision for the result of this operation. - * @return {@code this / divisor}. - * @throws NullPointerException - * if {@code divisor == null} or {@code mc == null}. - * @throws ArithmeticException - * if {@code divisor == 0}. - * @throws ArithmeticException - * if {@code mc.getRoundingMode() == UNNECESSARY} and rounding - * is necessary according {@code mc.getPrecision()}. - */ - public BigDecimal divide(BigDecimal divisor, MathContext mc) { - /* Calculating how many zeros must be append to 'dividend' - * to obtain a quotient with at least 'mc.precision()' digits */ - long trailingZeros = mc.getPrecision() + 2L - + divisor.approxPrecision() - approxPrecision(); - long diffScale = (long)scale - divisor.scale; - long newScale = diffScale; // scale of the final quotient - int compRem; // to compare the remainder - int i = 1; // index - int lastPow = TEN_POW.length - 1; // last power of ten - BigInteger integerQuot; // for temporal results - BigInteger quotAndRem[] = {getUnscaledValue()}; - // In special cases it reduces the problem to call the dual method - if ((mc.getPrecision() == 0) || (this.isZero()) - || (divisor.isZero())) { - return this.divide(divisor); - } - if (trailingZeros > 0) { - // To append trailing zeros at end of dividend - quotAndRem[0] = getUnscaledValue().multiply( Multiplication.powerOf10(trailingZeros) ); - newScale += trailingZeros; - } - quotAndRem = quotAndRem[0].divideAndRemainder( divisor.getUnscaledValue() ); - integerQuot = quotAndRem[0]; - // Calculating the exact quotient with at least 'mc.precision()' digits - if (quotAndRem[1].signum() != 0) { - // Checking if: 2 * remainder >= divisor ? - compRem = quotAndRem[1].shiftLeftOneBit().compareTo( divisor.getUnscaledValue() ); - // quot := quot * 10 + r; with 'r' in {-6,-5,-4, 0,+4,+5,+6} - integerQuot = integerQuot.multiply(BigInteger.TEN) - .add(BigInteger.valueOf(quotAndRem[0].signum() * (5 + compRem))); - newScale++; - } else { - // To strip trailing zeros until the preferred scale is reached - while (!integerQuot.testBit(0)) { - quotAndRem = integerQuot.divideAndRemainder(TEN_POW[i]); - if ((quotAndRem[1].signum() == 0) - && (newScale - i >= diffScale)) { - newScale -= i; - if (i < lastPow) { - i++; - } - integerQuot = quotAndRem[0]; - } else { - if (i == 1) { - break; - } - i = 1; - } - } - } - // To perform rounding - return new BigDecimal(integerQuot, safeLongToInt(newScale), mc); - } - - /** - * Returns a new {@code BigDecimal} whose value is the integral part of - * {@code this / divisor}. The quotient is rounded down towards zero to the - * next integer. For example, {@code 0.5/0.2 = 2}. - * - * @param divisor - * value by which {@code this} is divided. - * @return integral part of {@code this / divisor}. - * @throws NullPointerException - * if {@code divisor == null}. - * @throws ArithmeticException - * if {@code divisor == 0}. - */ - public BigDecimal divideToIntegralValue(BigDecimal divisor) { - BigInteger integralValue; // the integer of result - BigInteger powerOfTen; // some power of ten - - long newScale = (long)this.scale - divisor.scale; - long tempScale = 0; - int i = 1; - int lastPow = TEN_POW.length - 1; - - if (divisor.isZero()) { - throw new ArithmeticException("Division by zero"); - } - if ((divisor.approxPrecision() + newScale > this.approxPrecision() + 1L) - || (this.isZero())) { - /* If the divisor's integer part is greater than this's integer part, - * the result must be zero with the appropriate scale */ - integralValue = BigInteger.ZERO; - } else if (newScale == 0) { - integralValue = getUnscaledValue().divide( divisor.getUnscaledValue() ); - } else if (newScale > 0) { - powerOfTen = Multiplication.powerOf10(newScale); - integralValue = getUnscaledValue().divide( divisor.getUnscaledValue().multiply(powerOfTen) ); - integralValue = integralValue.multiply(powerOfTen); - } else {// (newScale < 0) - powerOfTen = Multiplication.powerOf10(-newScale); - integralValue = getUnscaledValue().multiply(powerOfTen).divide( divisor.getUnscaledValue() ); - // To strip trailing zeros approximating to the preferred scale - while (!integralValue.testBit(0)) { - BigInteger[] quotAndRem = integralValue.divideAndRemainder(TEN_POW[i]); - if ((quotAndRem[1].signum() == 0) - && (tempScale - i >= newScale)) { - tempScale -= i; - if (i < lastPow) { - i++; - } - integralValue = quotAndRem[0]; - } else { - if (i == 1) { - break; - } - i = 1; - } - } - newScale = tempScale; - } - return ((integralValue.signum() == 0) - ? zeroScaledBy(newScale) - : new BigDecimal(integralValue, safeLongToInt(newScale))); - } - - /** - * Returns a new {@code BigDecimal} whose value is the integral part of - * {@code this / divisor}. The quotient is rounded down towards zero to the - * next integer. The rounding mode passed with the parameter {@code mc} is - * not considered. But if the precision of {@code mc > 0} and the integral - * part requires more digits, then an {@code ArithmeticException} is thrown. - * - * @param divisor - * value by which {@code this} is divided. - * @param mc - * math context which determines the maximal precision of the - * result. - * @return integral part of {@code this / divisor}. - * @throws NullPointerException - * if {@code divisor == null} or {@code mc == null}. - * @throws ArithmeticException - * if {@code divisor == 0}. - * @throws ArithmeticException - * if {@code mc.getPrecision() > 0} and the result requires more - * digits to be represented. - */ - public BigDecimal divideToIntegralValue(BigDecimal divisor, MathContext mc) { - int mcPrecision = mc.getPrecision(); - int diffPrecision = this.precision() - divisor.precision(); - int lastPow = TEN_POW.length - 1; - long diffScale = (long)this.scale - divisor.scale; - long newScale = diffScale; - long quotPrecision = diffPrecision - diffScale + 1; - BigInteger quotAndRem[] = new BigInteger[2]; - // In special cases it call the dual method - if ((mcPrecision == 0) || (this.isZero()) || (divisor.isZero())) { - return this.divideToIntegralValue(divisor); - } - // Let be: this = [u1,s1] and divisor = [u2,s2] - if (quotPrecision <= 0) { - quotAndRem[0] = BigInteger.ZERO; - } else if (diffScale == 0) { - // CASE s1 == s2: to calculate u1 / u2 - quotAndRem[0] = this.getUnscaledValue().divide( divisor.getUnscaledValue() ); - } else if (diffScale > 0) { - // CASE s1 >= s2: to calculate u1 / (u2 * 10^(s1-s2) - quotAndRem[0] = this.getUnscaledValue().divide( - divisor.getUnscaledValue().multiply(Multiplication.powerOf10(diffScale)) ); - // To chose 10^newScale to get a quotient with at least 'mc.precision()' digits - newScale = Math.min(diffScale, Math.max(mcPrecision - quotPrecision + 1, 0)); - // To calculate: (u1 / (u2 * 10^(s1-s2)) * 10^newScale - quotAndRem[0] = quotAndRem[0].multiply(Multiplication.powerOf10(newScale)); - } else {// CASE s2 > s1: - /* To calculate the minimum power of ten, such that the quotient - * (u1 * 10^exp) / u2 has at least 'mc.precision()' digits. */ - long exp = Math.min(-diffScale, Math.max((long)mcPrecision - diffPrecision, 0)); - long compRemDiv; - // Let be: (u1 * 10^exp) / u2 = [q,r] - quotAndRem = this.getUnscaledValue().multiply(Multiplication.powerOf10(exp)). - divideAndRemainder(divisor.getUnscaledValue()); - newScale += exp; // To fix the scale - exp = -newScale; // The remaining power of ten - // If after division there is a remainder... - if ((quotAndRem[1].signum() != 0) && (exp > 0)) { - // Log10(r) + ((s2 - s1) - exp) > mc.precision ? - compRemDiv = (new BigDecimal(quotAndRem[1])).precision() - + exp - divisor.precision(); - if (compRemDiv == 0) { - // To calculate: (r * 10^exp2) / u2 - quotAndRem[1] = quotAndRem[1].multiply(Multiplication.powerOf10(exp)). - divide(divisor.getUnscaledValue()); - compRemDiv = Math.abs(quotAndRem[1].signum()); - } - if (compRemDiv > 0) { - throw new ArithmeticException("Division impossible"); - } - } - } - // Fast return if the quotient is zero - if (quotAndRem[0].signum() == 0) { - return zeroScaledBy(diffScale); - } - BigInteger strippedBI = quotAndRem[0]; - BigDecimal integralValue = new BigDecimal(quotAndRem[0]); - long resultPrecision = integralValue.precision(); - int i = 1; - // To strip trailing zeros until the specified precision is reached - while (!strippedBI.testBit(0)) { - quotAndRem = strippedBI.divideAndRemainder(TEN_POW[i]); - if ((quotAndRem[1].signum() == 0) && - ((resultPrecision - i >= mcPrecision) - || (newScale - i >= diffScale)) ) { - resultPrecision -= i; - newScale -= i; - if (i < lastPow) { - i++; - } - strippedBI = quotAndRem[0]; - } else { - if (i == 1) { - break; - } - i = 1; - } - } - // To check if the result fit in 'mc.precision()' digits - if (resultPrecision > mcPrecision) { - throw new ArithmeticException("Division impossible"); - } - integralValue.scale = safeLongToInt(newScale); - integralValue.setUnscaledValue(strippedBI); - return integralValue; - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this % divisor}. - * <p> - * The remainder is defined as {@code this - - * this.divideToIntegralValue(divisor) * divisor}. - * - * @param divisor - * value by which {@code this} is divided. - * @return {@code this % divisor}. - * @throws NullPointerException - * if {@code divisor == null}. - * @throws ArithmeticException - * if {@code divisor == 0}. - */ - public BigDecimal remainder(BigDecimal divisor) { - return divideAndRemainder(divisor)[1]; - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this % divisor}. - * <p> - * The remainder is defined as {@code this - - * this.divideToIntegralValue(divisor) * divisor}. - * <p> - * The specified rounding mode {@code mc} is used for the division only. - * - * @param divisor - * value by which {@code this} is divided. - * @param mc - * rounding mode and precision to be used. - * @return {@code this % divisor}. - * @throws NullPointerException - * if {@code divisor == null}. - * @throws ArithmeticException - * if {@code divisor == 0}. - * @throws ArithmeticException - * if {@code mc.getPrecision() > 0} and the result of {@code - * this.divideToIntegralValue(divisor, mc)} requires more digits - * to be represented. - */ - public BigDecimal remainder(BigDecimal divisor, MathContext mc) { - return divideAndRemainder(divisor, mc)[1]; - } - - /** - * Returns a {@code BigDecimal} array which contains the integral part of - * {@code this / divisor} at index 0 and the remainder {@code this % - * divisor} at index 1. The quotient is rounded down towards zero to the - * next integer. - * - * @param divisor - * value by which {@code this} is divided. - * @return {@code [this.divideToIntegralValue(divisor), - * this.remainder(divisor)]}. - * @throws NullPointerException - * if {@code divisor == null}. - * @throws ArithmeticException - * if {@code divisor == 0}. - * @see #divideToIntegralValue - * @see #remainder - */ - public BigDecimal[] divideAndRemainder(BigDecimal divisor) { - BigDecimal quotAndRem[] = new BigDecimal[2]; - - quotAndRem[0] = this.divideToIntegralValue(divisor); - quotAndRem[1] = this.subtract( quotAndRem[0].multiply(divisor) ); - return quotAndRem; - } - - /** - * Returns a {@code BigDecimal} array which contains the integral part of - * {@code this / divisor} at index 0 and the remainder {@code this % - * divisor} at index 1. The quotient is rounded down towards zero to the - * next integer. The rounding mode passed with the parameter {@code mc} is - * not considered. But if the precision of {@code mc > 0} and the integral - * part requires more digits, then an {@code ArithmeticException} is thrown. - * - * @param divisor - * value by which {@code this} is divided. - * @param mc - * math context which determines the maximal precision of the - * result. - * @return {@code [this.divideToIntegralValue(divisor), - * this.remainder(divisor)]}. - * @throws NullPointerException - * if {@code divisor == null}. - * @throws ArithmeticException - * if {@code divisor == 0}. - * @see #divideToIntegralValue - * @see #remainder - */ - public BigDecimal[] divideAndRemainder(BigDecimal divisor, MathContext mc) { - BigDecimal quotAndRem[] = new BigDecimal[2]; - - quotAndRem[0] = this.divideToIntegralValue(divisor, mc); - quotAndRem[1] = this.subtract( quotAndRem[0].multiply(divisor) ); - return quotAndRem; - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this<sup>n</sup>}. The - * scale of the result is {@code n * this.scale()}. - * - * <p>{@code x.pow(0)} returns {@code 1}, even if {@code x == 0}. - * - * <p>Implementation Note: The implementation is based on the ANSI standard - * X3.274-1996 algorithm. - * - * @throws ArithmeticException - * if {@code n < 0} or {@code n > 999999999}. - */ - public BigDecimal pow(int n) { - if (n == 0) { - return ONE; - } - if ((n < 0) || (n > 999999999)) { - throw new ArithmeticException("Invalid operation"); - } - long newScale = scale * (long)n; - // Let be: this = [u,s] so: this^n = [u^n, s*n] - return isZero() ? zeroScaledBy(newScale) - : new BigDecimal(getUnscaledValue().pow(n), safeLongToInt(newScale)); - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this<sup>n</sup>}. The - * result is rounded according to the passed context {@code mc}. - * - * <p>Implementation Note: The implementation is based on the ANSI standard - * X3.274-1996 algorithm. - * - * @param mc - * rounding mode and precision for the result of this operation. - * @throws ArithmeticException - * if {@code n < 0} or {@code n > 999999999}. - */ - public BigDecimal pow(int n, MathContext mc) { - // The ANSI standard X3.274-1996 algorithm - int m = Math.abs(n); - int mcPrecision = mc.getPrecision(); - int elength = (int)Math.log10(m) + 1; // decimal digits in 'n' - int oneBitMask; // mask of bits - BigDecimal accum; // the single accumulator - MathContext newPrecision = mc; // MathContext by default - - // In particular cases, it reduces the problem to call the other 'pow()' - if ((n == 0) || ((isZero()) && (n > 0))) { - return pow(n); - } - if ((m > 999999999) || ((mcPrecision == 0) && (n < 0)) - || ((mcPrecision > 0) && (elength > mcPrecision))) { - throw new ArithmeticException("Invalid operation"); - } - if (mcPrecision > 0) { - newPrecision = new MathContext( mcPrecision + elength + 1, - mc.getRoundingMode()); - } - // The result is calculated as if 'n' were positive - accum = round(newPrecision); - oneBitMask = Integer.highestOneBit(m) >> 1; - - while (oneBitMask > 0) { - accum = accum.multiply(accum, newPrecision); - if ((m & oneBitMask) == oneBitMask) { - accum = accum.multiply(this, newPrecision); - } - oneBitMask >>= 1; - } - // If 'n' is negative, the value is divided into 'ONE' - if (n < 0) { - accum = ONE.divide(accum, newPrecision); - } - // The final value is rounded to the destination precision - accum.inplaceRound(mc); - return accum; - } - - /** - * Returns a {@code BigDecimal} whose value is the absolute value of - * {@code this}. The scale of the result is the same as the scale of this. - */ - public BigDecimal abs() { - return ((signum() < 0) ? negate() : this); - } - - /** - * Returns a {@code BigDecimal} whose value is the absolute value of - * {@code this}. The result is rounded according to the passed context - * {@code mc}. - */ - public BigDecimal abs(MathContext mc) { - BigDecimal result = (signum() < 0) ? negate() : new BigDecimal(getUnscaledValue(), scale); - result.inplaceRound(mc); - return result; - } - - /** - * Returns a new {@code BigDecimal} whose value is the {@code -this}. The - * scale of the result is the same as the scale of this. - * - * @return {@code -this} - */ - public BigDecimal negate() { - if(bitLength < 63 || (bitLength == 63 && smallValue!=Long.MIN_VALUE)) { - return valueOf(-smallValue,scale); - } - return new BigDecimal(getUnscaledValue().negate(), scale); - } - - /** - * Returns a new {@code BigDecimal} whose value is the {@code -this}. The - * result is rounded according to the passed context {@code mc}. - * - * @param mc - * rounding mode and precision for the result of this operation. - * @return {@code -this} - */ - public BigDecimal negate(MathContext mc) { - BigDecimal result = negate(); - result.inplaceRound(mc); - return result; - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code +this}. The scale - * of the result is the same as the scale of this. - * - * @return {@code this} - */ - public BigDecimal plus() { - return this; - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code +this}. The result - * is rounded according to the passed context {@code mc}. - * - * @param mc - * rounding mode and precision for the result of this operation. - * @return {@code this}, rounded - */ - public BigDecimal plus(MathContext mc) { - return round(mc); - } - - /** - * Returns the sign of this {@code BigDecimal}. - * - * @return {@code -1} if {@code this < 0}, - * {@code 0} if {@code this == 0}, - * {@code 1} if {@code this > 0}. - */ - public int signum() { - if( bitLength < 64) { - return Long.signum( this.smallValue ); - } - return getUnscaledValue().signum(); - } - - private boolean isZero() { - //Watch out: -1 has a bitLength=0 - return bitLength == 0 && this.smallValue != -1; - } - - /** - * Returns the scale of this {@code BigDecimal}. The scale is the number of - * digits behind the decimal point. The value of this {@code BigDecimal} is - * the {@code unsignedValue * 10<sup>-scale</sup>}. If the scale is negative, - * then this {@code BigDecimal} represents a big integer. - * - * @return the scale of this {@code BigDecimal}. - */ - public int scale() { - return scale; - } - - /** - * Returns the precision of this {@code BigDecimal}. The precision is the - * number of decimal digits used to represent this decimal. It is equivalent - * to the number of digits of the unscaled value. The precision of {@code 0} - * is {@code 1} (independent of the scale). - * - * @return the precision of this {@code BigDecimal}. - */ - public int precision() { - // Return the cached value if we have one. - if (precision != 0) { - return precision; - } - - if (bitLength == 0) { - precision = 1; - } else if (bitLength < 64) { - precision = decimalDigitsInLong(smallValue); - } else { - int decimalDigits = 1 + (int) ((bitLength - 1) * LOG10_2); - // If after division the number isn't zero, there exists an additional digit - if (getUnscaledValue().divide(Multiplication.powerOf10(decimalDigits)).signum() != 0) { - decimalDigits++; - } - precision = decimalDigits; - } - return precision; - } - - private int decimalDigitsInLong(long value) { - if (value == Long.MIN_VALUE) { - return 19; // special case required because abs(MIN_VALUE) == MIN_VALUE - } else { - int index = Arrays.binarySearch(MathUtils.LONG_POWERS_OF_TEN, Math.abs(value)); - return (index < 0) ? (-index - 1) : (index + 1); - } - } - - /** - * Returns the unscaled value (mantissa) of this {@code BigDecimal} instance - * as a {@code BigInteger}. The unscaled value can be computed as - * {@code this * 10<sup>scale</sup>}. - */ - public BigInteger unscaledValue() { - return getUnscaledValue(); - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this}, rounded - * according to the passed context {@code mc}. - * <p> - * If {@code mc.precision = 0}, then no rounding is performed. - * <p> - * If {@code mc.precision > 0} and {@code mc.roundingMode == UNNECESSARY}, - * then an {@code ArithmeticException} is thrown if the result cannot be - * represented exactly within the given precision. - * - * @param mc - * rounding mode and precision for the result of this operation. - * @return {@code this} rounded according to the passed context. - * @throws ArithmeticException - * if {@code mc.precision > 0} and {@code mc.roundingMode == - * UNNECESSARY} and this cannot be represented within the given - * precision. - */ - public BigDecimal round(MathContext mc) { - BigDecimal thisBD = new BigDecimal(getUnscaledValue(), scale); - - thisBD.inplaceRound(mc); - return thisBD; - } - - /** - * Returns a new {@code BigDecimal} instance with the specified scale. - * <p> - * If the new scale is greater than the old scale, then additional zeros are - * added to the unscaled value. In this case no rounding is necessary. - * <p> - * If the new scale is smaller than the old scale, then trailing digits are - * removed. If these trailing digits are not zero, then the remaining - * unscaled value has to be rounded. For this rounding operation the - * specified rounding mode is used. - * - * @param newScale - * scale of the result returned. - * @param roundingMode - * rounding mode to be used to round the result. - * @return a new {@code BigDecimal} instance with the specified scale. - * @throws NullPointerException - * if {@code roundingMode == null}. - * @throws ArithmeticException - * if {@code roundingMode == ROUND_UNNECESSARY} and rounding is - * necessary according to the given scale. - */ - public BigDecimal setScale(int newScale, RoundingMode roundingMode) { - if (roundingMode == null) { - throw new NullPointerException("roundingMode == null"); - } - long diffScale = newScale - (long)scale; - // Let be: 'this' = [u,s] - if(diffScale == 0) { - return this; - } - if(diffScale > 0) { - // return [u * 10^(s2 - s), newScale] - if(diffScale < MathUtils.LONG_POWERS_OF_TEN.length && - (this.bitLength + LONG_POWERS_OF_TEN_BIT_LENGTH[(int)diffScale]) < 64 ) { - return valueOf(this.smallValue*MathUtils.LONG_POWERS_OF_TEN[(int)diffScale],newScale); - } - return new BigDecimal(Multiplication.multiplyByTenPow(getUnscaledValue(),(int)diffScale), newScale); - } - // diffScale < 0 - // return [u,s] / [1,newScale] with the appropriate scale and rounding - if(this.bitLength < 64 && -diffScale < MathUtils.LONG_POWERS_OF_TEN.length) { - return dividePrimitiveLongs(this.smallValue, MathUtils.LONG_POWERS_OF_TEN[(int)-diffScale], newScale,roundingMode); - } - return divideBigIntegers(this.getUnscaledValue(),Multiplication.powerOf10(-diffScale),newScale,roundingMode); - } - - /** - * Returns a new {@code BigDecimal} instance with the specified scale. - * <p> - * If the new scale is greater than the old scale, then additional zeros are - * added to the unscaled value. In this case no rounding is necessary. - * <p> - * If the new scale is smaller than the old scale, then trailing digits are - * removed. If these trailing digits are not zero, then the remaining - * unscaled value has to be rounded. For this rounding operation the - * specified rounding mode is used. - * - * @param newScale - * scale of the result returned. - * @param roundingMode - * rounding mode to be used to round the result. - * @return a new {@code BigDecimal} instance with the specified scale. - * @throws IllegalArgumentException - * if {@code roundingMode} is not a valid rounding mode. - * @throws ArithmeticException - * if {@code roundingMode == ROUND_UNNECESSARY} and rounding is - * necessary according to the given scale. - */ - public BigDecimal setScale(int newScale, int roundingMode) { - return setScale(newScale, RoundingMode.valueOf(roundingMode)); - } - - /** - * Returns a new {@code BigDecimal} instance with the specified scale. If - * the new scale is greater than the old scale, then additional zeros are - * added to the unscaled value. If the new scale is smaller than the old - * scale, then trailing zeros are removed. If the trailing digits are not - * zeros then an ArithmeticException is thrown. - * <p> - * If no exception is thrown, then the following equation holds: {@code - * x.setScale(s).compareTo(x) == 0}. - * - * @param newScale - * scale of the result returned. - * @return a new {@code BigDecimal} instance with the specified scale. - * @throws ArithmeticException - * if rounding would be necessary. - */ - public BigDecimal setScale(int newScale) { - return setScale(newScale, RoundingMode.UNNECESSARY); - } - - /** - * Returns a new {@code BigDecimal} instance where the decimal point has - * been moved {@code n} places to the left. If {@code n < 0} then the - * decimal point is moved {@code -n} places to the right. - * - * <p>The result is obtained by changing its scale. If the scale of the result - * becomes negative, then its precision is increased such that the scale is - * zero. - * - * <p>Note, that {@code movePointLeft(0)} returns a result which is - * mathematically equivalent, but which has {@code scale >= 0}. - */ - public BigDecimal movePointLeft(int n) { - return movePoint(scale + (long)n); - } - - private BigDecimal movePoint(long newScale) { - if (isZero()) { - return zeroScaledBy(Math.max(newScale, 0)); - } - /* - * When: 'n'== Integer.MIN_VALUE isn't possible to call to - * movePointRight(-n) since -Integer.MIN_VALUE == Integer.MIN_VALUE - */ - if(newScale >= 0) { - if(bitLength < 64) { - return valueOf(smallValue, safeLongToInt(newScale)); - } - return new BigDecimal(getUnscaledValue(), safeLongToInt(newScale)); - } - if(-newScale < MathUtils.LONG_POWERS_OF_TEN.length && - bitLength + LONG_POWERS_OF_TEN_BIT_LENGTH[(int)-newScale] < 64 ) { - return valueOf(smallValue*MathUtils.LONG_POWERS_OF_TEN[(int)-newScale],0); - } - return new BigDecimal(Multiplication.multiplyByTenPow( - getUnscaledValue(), safeLongToInt(-newScale)), 0); - } - - /** - * Returns a new {@code BigDecimal} instance where the decimal point has - * been moved {@code n} places to the right. If {@code n < 0} then the - * decimal point is moved {@code -n} places to the left. - * - * <p>The result is obtained by changing its scale. If the scale of the result - * becomes negative, then its precision is increased such that the scale is - * zero. - * - * <p>Note, that {@code movePointRight(0)} returns a result which is - * mathematically equivalent, but which has scale >= 0. - */ - public BigDecimal movePointRight(int n) { - return movePoint(scale - (long)n); - } - - /** - * Returns a new {@code BigDecimal} whose value is {@code this * 10<sup>n</sup>}. - * The scale of the result is {@code this.scale()} - {@code n}. - * The precision of the result is the precision of {@code this}. - * - * <p>This method has the same effect as {@link #movePointRight}, except that - * the precision is not changed. - */ - public BigDecimal scaleByPowerOfTen(int n) { - long newScale = scale - (long)n; - if(bitLength < 64) { - //Taking care when a 0 is to be scaled - if( smallValue==0 ){ - return zeroScaledBy( newScale ); - } - return valueOf(smallValue, safeLongToInt(newScale)); - } - return new BigDecimal(getUnscaledValue(), safeLongToInt(newScale)); - } - - /** - * Returns a new {@code BigDecimal} instance with the same value as {@code - * this} but with a unscaled value where the trailing zeros have been - * removed. If the unscaled value of {@code this} has n trailing zeros, then - * the scale and the precision of the result has been reduced by n. - * - * @return a new {@code BigDecimal} instance equivalent to this where the - * trailing zeros of the unscaled value have been removed. - */ - public BigDecimal stripTrailingZeros() { - int i = 1; // 1 <= i <= 18 - int lastPow = TEN_POW.length - 1; - long newScale = scale; - - if (isZero()) { - return new BigDecimal(BigInteger.ZERO, 0); - } - BigInteger strippedBI = getUnscaledValue(); - BigInteger[] quotAndRem; - - // while the number is even... - while (!strippedBI.testBit(0)) { - // To divide by 10^i - quotAndRem = strippedBI.divideAndRemainder(TEN_POW[i]); - // To look the remainder - if (quotAndRem[1].signum() == 0) { - // To adjust the scale - newScale -= i; - if (i < lastPow) { - // To set to the next power - i++; - } - strippedBI = quotAndRem[0]; - } else { - if (i == 1) { - // 'this' has no more trailing zeros - break; - } - // To set to the smallest power of ten - i = 1; - } - } - return new BigDecimal(strippedBI, safeLongToInt(newScale)); - } - - /** - * Compares this {@code BigDecimal} with {@code val}. Returns one of the - * three values {@code 1}, {@code 0}, or {@code -1}. The method behaves as - * if {@code this.subtract(val)} is computed. If this difference is > 0 then - * 1 is returned, if the difference is < 0 then -1 is returned, and if the - * difference is 0 then 0 is returned. This means, that if two decimal - * instances are compared which are equal in value but differ in scale, then - * these two instances are considered as equal. - * - * @param val - * value to be compared with {@code this}. - * @return {@code 1} if {@code this > val}, {@code -1} if {@code this < val}, - * {@code 0} if {@code this == val}. - * @throws NullPointerException - * if {@code val == null}. - */ - public int compareTo(BigDecimal val) { - int thisSign = signum(); - int valueSign = val.signum(); - - if( thisSign == valueSign) { - if(this.scale == val.scale && this.bitLength<64 && val.bitLength<64 ) { - return (smallValue < val.smallValue) ? -1 : (smallValue > val.smallValue) ? 1 : 0; - } - long diffScale = (long)this.scale - val.scale; - int diffPrecision = this.approxPrecision() - val.approxPrecision(); - if (diffPrecision > diffScale + 1) { - return thisSign; - } else if (diffPrecision < diffScale - 1) { - return -thisSign; - } else {// thisSign == val.signum() and diffPrecision is aprox. diffScale - BigInteger thisUnscaled = this.getUnscaledValue(); - BigInteger valUnscaled = val.getUnscaledValue(); - // If any of both precision is bigger, append zeros to the shorter one - if (diffScale < 0) { - thisUnscaled = thisUnscaled.multiply(Multiplication.powerOf10(-diffScale)); - } else if (diffScale > 0) { - valUnscaled = valUnscaled.multiply(Multiplication.powerOf10(diffScale)); - } - return thisUnscaled.compareTo(valUnscaled); - } - } else if (thisSign < valueSign) { - return -1; - } else { - return 1; - } - } - - /** - * Returns {@code true} if {@code x} is a {@code BigDecimal} instance and if - * this instance is equal to this big decimal. Two big decimals are equal if - * their unscaled value and their scale is equal. For example, 1.0 - * (10*10<sup>-1</sup>) is not equal to 1.00 (100*10<sup>-2</sup>). Similarly, zero - * instances are not equal if their scale differs. - */ - @Override - public boolean equals(Object x) { - if (this == x) { - return true; - } - if (x instanceof BigDecimal) { - BigDecimal x1 = (BigDecimal) x; - return x1.scale == scale - && x1.bitLength == bitLength - && (bitLength < 64 ? (x1.smallValue == smallValue) : x1.intVal.equals(intVal)); - } - return false; - } - - /** - * Returns the minimum of this {@code BigDecimal} and {@code val}. - * - * @param val - * value to be used to compute the minimum with this. - * @return {@code min(this, val}. - * @throws NullPointerException - * if {@code val == null}. - */ - public BigDecimal min(BigDecimal val) { - return ((compareTo(val) <= 0) ? this : val); - } - - /** - * Returns the maximum of this {@code BigDecimal} and {@code val}. - * - * @param val - * value to be used to compute the maximum with this. - * @return {@code max(this, val}. - * @throws NullPointerException - * if {@code val == null}. - */ - public BigDecimal max(BigDecimal val) { - return ((compareTo(val) >= 0) ? this : val); - } - - /** - * Returns a hash code for this {@code BigDecimal}. - * - * @return hash code for {@code this}. - */ - @Override - public int hashCode() { - if (hashCode != 0) { - return hashCode; - } - if (bitLength < 64) { - hashCode = (int)(smallValue & 0xffffffff); - hashCode = 33 * hashCode + (int)((smallValue >> 32) & 0xffffffff); - hashCode = 17 * hashCode + scale; - return hashCode; - } - hashCode = 17 * intVal.hashCode() + scale; - return hashCode; - } - - /** - * Returns a canonical string representation of this {@code BigDecimal}. If - * necessary, scientific notation is used. This representation always prints - * all significant digits of this value. - * <p> - * If the scale is negative or if {@code scale - precision >= 6} then - * scientific notation is used. - * - * @return a string representation of {@code this} in scientific notation if - * necessary. - */ - @Override - public String toString() { - if (toStringImage != null) { - return toStringImage; - } - if(bitLength < 32) { - toStringImage = Conversion.toDecimalScaledString(smallValue,scale); - return toStringImage; - } - String intString = getUnscaledValue().toString(); - if (scale == 0) { - return intString; - } - int begin = (getUnscaledValue().signum() < 0) ? 2 : 1; - int end = intString.length(); - long exponent = -(long)scale + end - begin; - StringBuilder result = new StringBuilder(); - - result.append(intString); - if ((scale > 0) && (exponent >= -6)) { - if (exponent >= 0) { - result.insert(end - scale, '.'); - } else { - result.insert(begin - 1, "0."); - result.insert(begin + 1, CH_ZEROS, 0, -(int)exponent - 1); - } - } else { - if (end - begin >= 1) { - result.insert(begin, '.'); - end++; - } - result.insert(end, 'E'); - if (exponent > 0) { - result.insert(++end, '+'); - } - result.insert(++end, Long.toString(exponent)); - } - toStringImage = result.toString(); - return toStringImage; - } - - /** - * Returns a string representation of this {@code BigDecimal}. This - * representation always prints all significant digits of this value. - * <p> - * If the scale is negative or if {@code scale - precision >= 6} then - * engineering notation is used. Engineering notation is similar to the - * scientific notation except that the exponent is made to be a multiple of - * 3 such that the integer part is >= 1 and < 1000. - * - * @return a string representation of {@code this} in engineering notation - * if necessary. - */ - public String toEngineeringString() { - String intString = getUnscaledValue().toString(); - if (scale == 0) { - return intString; - } - int begin = (getUnscaledValue().signum() < 0) ? 2 : 1; - int end = intString.length(); - long exponent = -(long)scale + end - begin; - StringBuilder result = new StringBuilder(intString); - - if ((scale > 0) && (exponent >= -6)) { - if (exponent >= 0) { - result.insert(end - scale, '.'); - } else { - result.insert(begin - 1, "0."); - result.insert(begin + 1, CH_ZEROS, 0, -(int)exponent - 1); - } - } else { - int delta = end - begin; - int rem = (int)(exponent % 3); - - if (rem != 0) { - // adjust exponent so it is a multiple of three - if (getUnscaledValue().signum() == 0) { - // zero value - rem = (rem < 0) ? -rem : 3 - rem; - exponent += rem; - } else { - // nonzero value - rem = (rem < 0) ? rem + 3 : rem; - exponent -= rem; - begin += rem; - } - if (delta < 3) { - for (int i = rem - delta; i > 0; i--) { - result.insert(end++, '0'); - } - } - } - if (end - begin >= 1) { - result.insert(begin, '.'); - end++; - } - if (exponent != 0) { - result.insert(end, 'E'); - if (exponent > 0) { - result.insert(++end, '+'); - } - result.insert(++end, Long.toString(exponent)); - } - } - return result.toString(); - } - - /** - * Returns a string representation of this {@code BigDecimal}. No scientific - * notation is used. This methods adds zeros where necessary. - * <p> - * If this string representation is used to create a new instance, this - * instance is generally not identical to {@code this} as the precision - * changes. - * <p> - * {@code x.equals(new BigDecimal(x.toPlainString())} usually returns - * {@code false}. - * <p> - * {@code x.compareTo(new BigDecimal(x.toPlainString())} returns {@code 0}. - * - * @return a string representation of {@code this} without exponent part. - */ - public String toPlainString() { - String intStr = getUnscaledValue().toString(); - if ((scale == 0) || ((isZero()) && (scale < 0))) { - return intStr; - } - int begin = (signum() < 0) ? 1 : 0; - int delta = scale; - // We take space for all digits, plus a possible decimal point, plus 'scale' - StringBuilder result = new StringBuilder(intStr.length() + 1 + Math.abs(scale)); - - if (begin == 1) { - // If the number is negative, we insert a '-' character at front - result.append('-'); - } - if (scale > 0) { - delta -= (intStr.length() - begin); - if (delta >= 0) { - result.append("0."); - // To append zeros after the decimal point - for (; delta > CH_ZEROS.length; delta -= CH_ZEROS.length) { - result.append(CH_ZEROS); - } - result.append(CH_ZEROS, 0, delta); - result.append(intStr.substring(begin)); - } else { - delta = begin - delta; - result.append(intStr.substring(begin, delta)); - result.append('.'); - result.append(intStr.substring(delta)); - } - } else {// (scale <= 0) - result.append(intStr.substring(begin)); - // To append trailing zeros - for (; delta < -CH_ZEROS.length; delta += CH_ZEROS.length) { - result.append(CH_ZEROS); - } - result.append(CH_ZEROS, 0, -delta); - } - return result.toString(); - } - - /** - * Returns this {@code BigDecimal} as a big integer instance. A fractional - * part is discarded. - * - * @return this {@code BigDecimal} as a big integer instance. - */ - public BigInteger toBigInteger() { - if ((scale == 0) || (isZero())) { - return getUnscaledValue(); - } else if (scale < 0) { - return getUnscaledValue().multiply(Multiplication.powerOf10(-(long)scale)); - } else {// (scale > 0) - return getUnscaledValue().divide(Multiplication.powerOf10(scale)); - } - } - - /** - * Returns this {@code BigDecimal} as a big integer instance if it has no - * fractional part. If this {@code BigDecimal} has a fractional part, i.e. - * if rounding would be necessary, an {@code ArithmeticException} is thrown. - * - * @return this {@code BigDecimal} as a big integer value. - * @throws ArithmeticException - * if rounding is necessary. - */ - public BigInteger toBigIntegerExact() { - if ((scale == 0) || (isZero())) { - return getUnscaledValue(); - } else if (scale < 0) { - return getUnscaledValue().multiply(Multiplication.powerOf10(-(long)scale)); - } else {// (scale > 0) - BigInteger[] integerAndFraction; - // An optimization before do a heavy division - if ((scale > approxPrecision()) || (scale > getUnscaledValue().getLowestSetBit())) { - throw new ArithmeticException("Rounding necessary"); - } - integerAndFraction = getUnscaledValue().divideAndRemainder(Multiplication.powerOf10(scale)); - if (integerAndFraction[1].signum() != 0) { - // It exists a non-zero fractional part - throw new ArithmeticException("Rounding necessary"); - } - return integerAndFraction[0]; - } - } - - /** - * Returns this {@code BigDecimal} as an long value. Any fractional part is - * discarded. If the integral part of {@code this} is too big to be - * represented as an long, then {@code this % 2<sup>64</sup>} is returned. - */ - @Override - public long longValue() { - /* - * If scale <= -64 there are at least 64 trailing bits zero in - * 10^(-scale). If the scale is positive and very large the long value - * could be zero. - */ - return ((scale <= -64) || (scale > approxPrecision()) ? 0L : toBigInteger().longValue()); - } - - /** - * Returns this {@code BigDecimal} as a long value if it has no fractional - * part and if its value fits to the int range ([-2<sup>63</sup>..2<sup>63</sup>-1]). If - * these conditions are not met, an {@code ArithmeticException} is thrown. - * - * @throws ArithmeticException - * if rounding is necessary or the number doesn't fit in a long. - */ - public long longValueExact() { - return valueExact(64); - } - - /** - * Returns this {@code BigDecimal} as an int value. Any fractional part is - * discarded. If the integral part of {@code this} is too big to be - * represented as an int, then {@code this % 2<sup>32</sup>} is returned. - */ - @Override - public int intValue() { - /* - * If scale <= -32 there are at least 32 trailing bits zero in - * 10^(-scale). If the scale is positive and very large the long value - * could be zero. - */ - return ((scale <= -32) || (scale > approxPrecision()) ? 0 : toBigInteger().intValue()); - } - - /** - * Returns this {@code BigDecimal} as a int value if it has no fractional - * part and if its value fits to the int range ([-2<sup>31</sup>..2<sup>31</sup>-1]). If - * these conditions are not met, an {@code ArithmeticException} is thrown. - * - * @throws ArithmeticException - * if rounding is necessary or the number doesn't fit in an int. - */ - public int intValueExact() { - return (int) valueExact(32); - } - - /** - * Returns this {@code BigDecimal} as a short value if it has no fractional - * part and if its value fits to the short range ([-2<sup>15</sup>..2<sup>15</sup>-1]). If - * these conditions are not met, an {@code ArithmeticException} is thrown. - * - * @throws ArithmeticException - * if rounding is necessary of the number doesn't fit in a short. - */ - public short shortValueExact() { - return (short) valueExact(16); - } - - /** - * Returns this {@code BigDecimal} as a byte value if it has no fractional - * part and if its value fits to the byte range ([-128..127]). If these - * conditions are not met, an {@code ArithmeticException} is thrown. - * - * @throws ArithmeticException - * if rounding is necessary or the number doesn't fit in a byte. - */ - public byte byteValueExact() { - return (byte) valueExact(8); - } - - /** - * Returns this {@code BigDecimal} as a float value. If {@code this} is too - * big to be represented as an float, then {@code Float.POSITIVE_INFINITY} - * or {@code Float.NEGATIVE_INFINITY} is returned. - * <p> - * Note, that if the unscaled value has more than 24 significant digits, - * then this decimal cannot be represented exactly in a float variable. In - * this case the result is rounded. - * <p> - * For example, if the instance {@code x1 = new BigDecimal("0.1")} cannot be - * represented exactly as a float, and thus {@code x1.equals(new - * BigDecimal(x1.floatValue())} returns {@code false} for this case. - * <p> - * Similarly, if the instance {@code new BigDecimal(16777217)} is converted - * to a float, the result is {@code 1.6777216E}7. - * - * @return this {@code BigDecimal} as a float value. - */ - @Override - public float floatValue() { - /* A similar code like in doubleValue() could be repeated here, - * but this simple implementation is quite efficient. */ - float floatResult = signum(); - long powerOfTwo = this.bitLength - (long)(scale / LOG10_2); - if ((powerOfTwo < -149) || (floatResult == 0.0f)) { - // Cases which 'this' is very small - floatResult *= 0.0f; - } else if (powerOfTwo > 129) { - // Cases which 'this' is very large - floatResult *= Float.POSITIVE_INFINITY; - } else { - floatResult = (float)doubleValue(); - } - return floatResult; - } - - /** - * Returns this {@code BigDecimal} as a double value. If {@code this} is too - * big to be represented as an float, then {@code Double.POSITIVE_INFINITY} - * or {@code Double.NEGATIVE_INFINITY} is returned. - * <p> - * Note, that if the unscaled value has more than 53 significant digits, - * then this decimal cannot be represented exactly in a double variable. In - * this case the result is rounded. - * <p> - * For example, if the instance {@code x1 = new BigDecimal("0.1")} cannot be - * represented exactly as a double, and thus {@code x1.equals(new - * BigDecimal(x1.doubleValue())} returns {@code false} for this case. - * <p> - * Similarly, if the instance {@code new BigDecimal(9007199254740993L)} is - * converted to a double, the result is {@code 9.007199254740992E15}. - * <p> - * - * @return this {@code BigDecimal} as a double value. - */ - @Override - public double doubleValue() { - int sign = signum(); - int exponent = 1076; // bias + 53 - int lowestSetBit; - int discardedSize; - long powerOfTwo = this.bitLength - (long)(scale / LOG10_2); - long bits; // IEEE-754 Standard - long tempBits; // for temporal calculations - BigInteger mantissa; - - if ((powerOfTwo < -1074) || (sign == 0)) { - // Cases which 'this' is very small - return (sign * 0.0d); - } else if (powerOfTwo > 1025) { - // Cases which 'this' is very large - return (sign * Double.POSITIVE_INFINITY); - } - mantissa = getUnscaledValue().abs(); - // Let be: this = [u,s], with s > 0 - if (scale <= 0) { - // mantissa = abs(u) * 10^s - mantissa = mantissa.multiply(Multiplication.powerOf10(-scale)); - } else {// (scale > 0) - BigInteger quotAndRem[]; - BigInteger powerOfTen = Multiplication.powerOf10(scale); - int k = 100 - (int)powerOfTwo; - int compRem; - - if (k > 0) { - /* Computing (mantissa * 2^k) , where 'k' is a enough big - * power of '2' to can divide by 10^s */ - mantissa = mantissa.shiftLeft(k); - exponent -= k; - } - // Computing (mantissa * 2^k) / 10^s - quotAndRem = mantissa.divideAndRemainder(powerOfTen); - // To check if the fractional part >= 0.5 - compRem = quotAndRem[1].shiftLeftOneBit().compareTo(powerOfTen); - // To add two rounded bits at end of mantissa - mantissa = quotAndRem[0].shiftLeft(2).add( - BigInteger.valueOf((compRem * (compRem + 3)) / 2 + 1)); - exponent -= 2; - } - lowestSetBit = mantissa.getLowestSetBit(); - discardedSize = mantissa.bitLength() - 54; - if (discardedSize > 0) {// (n > 54) - // mantissa = (abs(u) * 10^s) >> (n - 54) - bits = mantissa.shiftRight(discardedSize).longValue(); - tempBits = bits; - // #bits = 54, to check if the discarded fraction produces a carry - if ((((bits & 1) == 1) && (lowestSetBit < discardedSize)) - || ((bits & 3) == 3)) { - bits += 2; - } - } else {// (n <= 54) - // mantissa = (abs(u) * 10^s) << (54 - n) - bits = mantissa.longValue() << -discardedSize; - tempBits = bits; - // #bits = 54, to check if the discarded fraction produces a carry: - if ((bits & 3) == 3) { - bits += 2; - } - } - // Testing bit 54 to check if the carry creates a new binary digit - if ((bits & 0x40000000000000L) == 0) { - // To drop the last bit of mantissa (first discarded) - bits >>= 1; - // exponent = 2^(s-n+53+bias) - exponent += discardedSize; - } else {// #bits = 54 - bits >>= 2; - exponent += discardedSize + 1; - } - // To test if the 53-bits number fits in 'double' - if (exponent > 2046) {// (exponent - bias > 1023) - return (sign * Double.POSITIVE_INFINITY); - } else if (exponent <= 0) {// (exponent - bias <= -1023) - // Denormalized numbers (having exponent == 0) - if (exponent < -53) {// exponent - bias < -1076 - return (sign * 0.0d); - } - // -1076 <= exponent - bias <= -1023 - // To discard '- exponent + 1' bits - bits = tempBits >> 1; - tempBits = bits & (-1L >>> (63 + exponent)); - bits >>= (-exponent ); - // To test if after discard bits, a new carry is generated - if (((bits & 3) == 3) || (((bits & 1) == 1) && (tempBits != 0) - && (lowestSetBit < discardedSize))) { - bits += 1; - } - exponent = 0; - bits >>= 1; - } - // Construct the 64 double bits: [sign(1), exponent(11), mantissa(52)] - bits = (sign & 0x8000000000000000L) | ((long)exponent << 52) - | (bits & 0xFFFFFFFFFFFFFL); - return Double.longBitsToDouble(bits); - } - - /** - * Returns the unit in the last place (ULP) of this {@code BigDecimal} - * instance. An ULP is the distance to the nearest big decimal with the same - * precision. - * - * <p>The amount of a rounding error in the evaluation of a floating-point - * operation is often expressed in ULPs. An error of 1 ULP is often seen as - * a tolerable error. - * - * <p>For class {@code BigDecimal}, the ULP of a number is simply 10<sup>-scale</sup>. - * For example, {@code new BigDecimal(0.1).ulp()} returns {@code 1E-55}. - * - * @return unit in the last place (ULP) of this {@code BigDecimal} instance. - */ - public BigDecimal ulp() { - return valueOf(1, scale); - } - - /* Private Methods */ - - /** - * It does all rounding work of the public method - * {@code round(MathContext)}, performing an inplace rounding - * without creating a new object. - * - * @param mc - * the {@code MathContext} for perform the rounding. - * @see #round(MathContext) - */ - private void inplaceRound(MathContext mc) { - int mcPrecision = mc.getPrecision(); - if (approxPrecision() < mcPrecision || mcPrecision == 0) { - return; - } - int discardedPrecision = precision() - mcPrecision; - // If no rounding is necessary it returns immediately - if ((discardedPrecision <= 0)) { - return; - } - // When the number is small perform an efficient rounding - if (this.bitLength < 64) { - smallRound(mc, discardedPrecision); - return; - } - // Getting the integer part and the discarded fraction - BigInteger sizeOfFraction = Multiplication.powerOf10(discardedPrecision); - BigInteger[] integerAndFraction = getUnscaledValue().divideAndRemainder(sizeOfFraction); - long newScale = (long)scale - discardedPrecision; - int compRem; - BigDecimal tempBD; - // If the discarded fraction is non-zero, perform rounding - if (integerAndFraction[1].signum() != 0) { - // To check if the discarded fraction >= 0.5 - compRem = (integerAndFraction[1].abs().shiftLeftOneBit().compareTo(sizeOfFraction)); - // To look if there is a carry - compRem = roundingBehavior( integerAndFraction[0].testBit(0) ? 1 : 0, - integerAndFraction[1].signum() * (5 + compRem), - mc.getRoundingMode()); - if (compRem != 0) { - integerAndFraction[0] = integerAndFraction[0].add(BigInteger.valueOf(compRem)); - } - tempBD = new BigDecimal(integerAndFraction[0]); - // If after to add the increment the precision changed, we normalize the size - if (tempBD.precision() > mcPrecision) { - integerAndFraction[0] = integerAndFraction[0].divide(BigInteger.TEN); - newScale--; - } - } - // To update all internal fields - scale = safeLongToInt(newScale); - precision = mcPrecision; - setUnscaledValue(integerAndFraction[0]); - } - - /** - * Returns -1, 0, and 1 if {@code value1 < value2}, {@code value1 == value2}, - * and {@code value1 > value2}, respectively, when comparing without regard - * to the values' sign. - * - * <p>Note that this implementation deals correctly with Long.MIN_VALUE, - * whose absolute magnitude is larger than any other {@code long} value. - */ - private static int compareAbsoluteValues(long value1, long value2) { - // Map long values to the range -1 .. Long.MAX_VALUE so that comparison - // of absolute magnitude can be done using regular long arithmetics. - // This deals correctly with Long.MIN_VALUE, whose absolute magnitude - // is larger than any other long value, and which is mapped to - // Long.MAX_VALUE here. - // Values that only differ by sign get mapped to the same value, for - // example both +3 and -3 get mapped to +2. - value1 = Math.abs(value1) - 1; - value2 = Math.abs(value2) - 1; - // Unlike Long.compare(), we guarantee to return specifically -1 and +1 - return value1 > value2 ? 1 : (value1 < value2 ? -1 : 0); - } - - /** - * Compares {@code n} against {@code 0.5 * d} in absolute terms (ignoring sign) - * and with arithmetics that are safe against overflow or loss of precision. - * Returns -1 if {@code n} is less than {@code 0.5 * d}, 0 if {@code n == 0.5 * d}, - * or +1 if {@code n > 0.5 * d} when comparing the absolute values under such - * arithmetics. - */ - private static int compareForRounding(long n, long d) { - long halfD = d / 2; // rounds towards 0 - if (n == halfD || n == -halfD) { - // In absolute terms: Because n == halfD, we know that 2 * n + lsb == d - // for some lsb value 0 or 1. This means that n == d/2 (result 0) if - // lsb is 0, or n < d/2 (result -1) if lsb is 1. In either case, the - // result is -lsb. - // Since we're calculating in absolute terms, we need the absolute lsb - // (d & 1) as opposed to the signed lsb (d % 2) which would be -1 for - // negative odd values of d. - int lsb = (int) d & 1; - return -lsb; // returns 0 or -1 - } else { - // In absolute terms, either 2 * n + 1 < d (in the case of n < halfD), - // or 2 * n > d (in the case of n > halfD). - // In either case, comparing n against halfD gets the right result - // -1 or +1, respectively. - return compareAbsoluteValues(n, halfD); - } - } - - /** - * This method implements an efficient rounding for numbers which unscaled - * value fits in the type {@code long}. - * - * @param mc - * the context to use - * @param discardedPrecision - * the number of decimal digits that are discarded - * @see #round(MathContext) - */ - private void smallRound(MathContext mc, int discardedPrecision) { - long sizeOfFraction = MathUtils.LONG_POWERS_OF_TEN[discardedPrecision]; - long newScale = (long)scale - discardedPrecision; - long unscaledVal = smallValue; - // Getting the integer part and the discarded fraction - long integer = unscaledVal / sizeOfFraction; - long fraction = unscaledVal % sizeOfFraction; - int compRem; - // If the discarded fraction is non-zero perform rounding - if (fraction != 0) { - // To check if the discarded fraction >= 0.5 - compRem = compareForRounding(fraction, sizeOfFraction); - // To look if there is a carry - integer += roundingBehavior( ((int)integer) & 1, - Long.signum(fraction) * (5 + compRem), - mc.getRoundingMode()); - // If after to add the increment the precision changed, we normalize the size - if (Math.log10(Math.abs(integer)) >= mc.getPrecision()) { - integer /= 10; - newScale--; - } - } - // To update all internal fields - scale = safeLongToInt(newScale); - precision = mc.getPrecision(); - smallValue = integer; - bitLength = bitLength(integer); - intVal = null; - } - - /** - * Return an increment that can be -1,0 or 1, depending of - * {@code roundingMode}. - * - * @param parityBit - * can be 0 or 1, it's only used in the case - * {@code HALF_EVEN} - * @param fraction - * the mantissa to be analyzed - * @param roundingMode - * the type of rounding - * @return the carry propagated after rounding - */ - private static int roundingBehavior(int parityBit, int fraction, RoundingMode roundingMode) { - int increment = 0; // the carry after rounding - - switch (roundingMode) { - case UNNECESSARY: - if (fraction != 0) { - throw new ArithmeticException("Rounding necessary"); - } - break; - case UP: - increment = Integer.signum(fraction); - break; - case DOWN: - break; - case CEILING: - increment = Math.max(Integer.signum(fraction), 0); - break; - case FLOOR: - increment = Math.min(Integer.signum(fraction), 0); - break; - case HALF_UP: - if (Math.abs(fraction) >= 5) { - increment = Integer.signum(fraction); - } - break; - case HALF_DOWN: - if (Math.abs(fraction) > 5) { - increment = Integer.signum(fraction); - } - break; - case HALF_EVEN: - if (Math.abs(fraction) + parityBit > 5) { - increment = Integer.signum(fraction); - } - break; - } - return increment; - } - - /** - * If {@code intVal} has a fractional part throws an exception, - * otherwise it counts the number of bits of value and checks if it's out of - * the range of the primitive type. If the number fits in the primitive type - * returns this number as {@code long}, otherwise throws an - * exception. - * - * @param bitLengthOfType - * number of bits of the type whose value will be calculated - * exactly - * @return the exact value of the integer part of {@code BigDecimal} - * when is possible - * @throws ArithmeticException when rounding is necessary or the - * number don't fit in the primitive type - */ - private long valueExact(int bitLengthOfType) { - BigInteger bigInteger = toBigIntegerExact(); - - if (bigInteger.bitLength() < bitLengthOfType) { - // It fits in the primitive type - return bigInteger.longValue(); - } - throw new ArithmeticException("Rounding necessary"); - } - - /** - * If the precision already was calculated it returns that value, otherwise - * it calculates a very good approximation efficiently . Note that this - * value will be {@code precision()} or {@code precision()-1} - * in the worst case. - * - * @return an approximation of {@code precision()} value - */ - private int approxPrecision() { - return precision > 0 - ? precision - : (int) ((this.bitLength - 1) * LOG10_2) + 1; - } - - private static int safeLongToInt(long longValue) { - if (longValue < Integer.MIN_VALUE || longValue > Integer.MAX_VALUE) { - throw new ArithmeticException("Out of int range: " + longValue); - } - return (int) longValue; - } - - /** - * It returns the value 0 with the most approximated scale of type - * {@code int}. if {@code longScale > Integer.MAX_VALUE} the - * scale will be {@code Integer.MAX_VALUE}; if - * {@code longScale < Integer.MIN_VALUE} the scale will be - * {@code Integer.MIN_VALUE}; otherwise {@code longScale} is - * casted to the type {@code int}. - * - * @param longScale - * the scale to which the value 0 will be scaled. - * @return the value 0 scaled by the closer scale of type {@code int}. - * @see #scale - */ - private static BigDecimal zeroScaledBy(long longScale) { - if (longScale == (int) longScale) { - return valueOf(0,(int)longScale); - } - if (longScale >= 0) { - return new BigDecimal( 0, Integer.MAX_VALUE); - } - return new BigDecimal( 0, Integer.MIN_VALUE); - } - - /** - * Assigns all transient fields upon deserialization of a - * {@code BigDecimal} instance (bitLength and smallValue). The transient - * field precision is assigned lazily. - */ - private void readObject(ObjectInputStream in) throws IOException, - ClassNotFoundException { - in.defaultReadObject(); - - this.bitLength = intVal.bitLength(); - if (this.bitLength < 64) { - this.smallValue = intVal.longValue(); - } - } - - /** - * Prepares this {@code BigDecimal} for serialization, i.e. the - * non-transient field {@code intVal} is assigned. - */ - private void writeObject(ObjectOutputStream out) throws IOException { - getUnscaledValue(); - out.defaultWriteObject(); - } - - private BigInteger getUnscaledValue() { - if(intVal == null) { - intVal = BigInteger.valueOf(smallValue); - } - return intVal; - } - - private void setUnscaledValue(BigInteger unscaledValue) { - this.intVal = unscaledValue; - this.bitLength = unscaledValue.bitLength(); - if(this.bitLength < 64) { - this.smallValue = unscaledValue.longValue(); - } - } - - private static int bitLength(long smallValue) { - if(smallValue < 0) { - smallValue = ~smallValue; - } - return 64 - Long.numberOfLeadingZeros(smallValue); - } - - private static int bitLength(int smallValue) { - if(smallValue < 0) { - smallValue = ~smallValue; - } - return 32 - Integer.numberOfLeadingZeros(smallValue); - } - -} diff --git a/luni/src/main/java/java/math/BigInt.java b/luni/src/main/java/java/math/BigInt.java deleted file mode 100644 index 4448ce18af..0000000000 --- a/luni/src/main/java/java/math/BigInt.java +++ /dev/null @@ -1,346 +0,0 @@ -/* - * Copyright (C) 2008 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package java.math; - -import dalvik.annotation.optimization.ReachabilitySensitive; -import libcore.util.NativeAllocationRegistry; - -/* - * In contrast to BigIntegers this class doesn't fake two's complement representation. - * Any Bit-Operations, including Shifting, solely regard the unsigned magnitude. - * Moreover BigInt objects are mutable and offer efficient in-place-operations. - */ -final class BigInt { - - private static NativeAllocationRegistry registry = NativeAllocationRegistry.createMalloced( - BigInt.class.getClassLoader(), NativeBN.getNativeFinalizer()); - - /* Fields used for the internal representation. */ - @ReachabilitySensitive - private transient long bignum = 0; - - @Override - public String toString() { - return this.decString(); - } - - boolean hasNativeBignum() { - return this.bignum != 0; - } - - private void makeValid() { - if (this.bignum == 0) { - this.bignum = NativeBN.BN_new(); - registry.registerNativeAllocation(this, this.bignum); - } - } - - private static BigInt newBigInt() { - BigInt bi = new BigInt(); - bi.bignum = NativeBN.BN_new(); - registry.registerNativeAllocation(bi, bi.bignum); - return bi; - } - - - static int cmp(BigInt a, BigInt b) { - return NativeBN.BN_cmp(a.bignum, b.bignum); - } - - - void putCopy(BigInt from) { - this.makeValid(); - NativeBN.BN_copy(this.bignum, from.bignum); - } - - BigInt copy() { - BigInt bi = new BigInt(); - bi.putCopy(this); - return bi; - } - - - void putLongInt(long val) { - this.makeValid(); - NativeBN.putLongInt(this.bignum, val); - } - - void putULongInt(long val, boolean neg) { - this.makeValid(); - NativeBN.putULongInt(this.bignum, val, neg); - } - - private NumberFormatException invalidBigInteger(String s) { - throw new NumberFormatException("Invalid BigInteger: " + s); - } - - void putDecString(String original) { - String s = checkString(original, 10); - this.makeValid(); - int usedLen = NativeBN.BN_dec2bn(this.bignum, s); - if (usedLen < s.length()) { - throw invalidBigInteger(original); - } - } - - void putHexString(String original) { - String s = checkString(original, 16); - this.makeValid(); - int usedLen = NativeBN.BN_hex2bn(this.bignum, s); - if (usedLen < s.length()) { - throw invalidBigInteger(original); - } - } - - /** - * Returns a string suitable for passing to OpenSSL. - * Throws if 's' doesn't match Java's rules for valid BigInteger strings. - * BN_dec2bn and BN_hex2bn do very little checking, so we need to manually - * ensure we comply with Java's rules. - * http://code.google.com/p/android/issues/detail?id=7036 - */ - String checkString(String s, int base) { - if (s == null) { - throw new NullPointerException("s == null"); - } - // A valid big integer consists of an optional '-' or '+' followed by - // one or more digit characters appropriate to the given base, - // and no other characters. - int charCount = s.length(); - int i = 0; - if (charCount > 0) { - char ch = s.charAt(0); - if (ch == '+') { - // Java supports leading +, but OpenSSL doesn't, so we need to strip it. - s = s.substring(1); - --charCount; - } else if (ch == '-') { - ++i; - } - } - if (charCount - i == 0) { - throw invalidBigInteger(s); - } - boolean nonAscii = false; - for (; i < charCount; ++i) { - char ch = s.charAt(i); - if (Character.digit(ch, base) == -1) { - throw invalidBigInteger(s); - } - if (ch > 128) { - nonAscii = true; - } - } - return nonAscii ? toAscii(s, base) : s; - } - - // Java supports non-ASCII decimal digits, but OpenSSL doesn't. - // We need to translate the decimal digits but leave any other characters alone. - // This method assumes it's being called on a string that has already been validated. - private static String toAscii(String s, int base) { - int length = s.length(); - StringBuilder result = new StringBuilder(length); - for (int i = 0; i < length; ++i) { - char ch = s.charAt(i); - int value = Character.digit(ch, base); - if (value >= 0 && value <= 9) { - ch = (char) ('0' + value); - } - result.append(ch); - } - return result.toString(); - } - - void putBigEndian(byte[] a, boolean neg) { - this.makeValid(); - NativeBN.BN_bin2bn(a, a.length, neg, this.bignum); - } - - void putLittleEndianInts(int[] a, boolean neg) { - this.makeValid(); - NativeBN.litEndInts2bn(a, a.length, neg, this.bignum); - } - - void putBigEndianTwosComplement(byte[] a) { - this.makeValid(); - NativeBN.twosComp2bn(a, a.length, this.bignum); - } - - - long longInt() { - return NativeBN.longInt(this.bignum); - } - - String decString() { - return NativeBN.BN_bn2dec(this.bignum); - } - - String hexString() { - return NativeBN.BN_bn2hex(this.bignum); - } - - byte[] bigEndianMagnitude() { - return NativeBN.BN_bn2bin(this.bignum); - } - - int[] littleEndianIntsMagnitude() { - return NativeBN.bn2litEndInts(this.bignum); - } - - int sign() { - return NativeBN.sign(this.bignum); - } - - void setSign(int val) { - if (val > 0) { - NativeBN.BN_set_negative(this.bignum, 0); - } else { - if (val < 0) NativeBN.BN_set_negative(this.bignum, 1); - } - } - - boolean twosCompFitsIntoBytes(int desiredByteCount) { - int actualByteCount = (NativeBN.bitLength(this.bignum) + 7) / 8; - return actualByteCount <= desiredByteCount; - } - - int bitLength() { - return NativeBN.bitLength(this.bignum); - } - - boolean isBitSet(int n) { - return NativeBN.BN_is_bit_set(this.bignum, n); - } - - // n > 0: shift left (multiply) - static BigInt shift(BigInt a, int n) { - BigInt r = newBigInt(); - NativeBN.BN_shift(r.bignum, a.bignum, n); - return r; - } - - void shift(int n) { - NativeBN.BN_shift(this.bignum, this.bignum, n); - } - - void addPositiveInt(int w) { - NativeBN.BN_add_word(this.bignum, w); - } - - void multiplyByPositiveInt(int w) { - NativeBN.BN_mul_word(this.bignum, w); - } - - static int remainderByPositiveInt(BigInt a, int w) { - return NativeBN.BN_mod_word(a.bignum, w); - } - - static BigInt addition(BigInt a, BigInt b) { - BigInt r = newBigInt(); - NativeBN.BN_add(r.bignum, a.bignum, b.bignum); - return r; - } - - void add(BigInt a) { - NativeBN.BN_add(this.bignum, this.bignum, a.bignum); - } - - static BigInt subtraction(BigInt a, BigInt b) { - BigInt r = newBigInt(); - NativeBN.BN_sub(r.bignum, a.bignum, b.bignum); - return r; - } - - - static BigInt gcd(BigInt a, BigInt b) { - BigInt r = newBigInt(); - NativeBN.BN_gcd(r.bignum, a.bignum, b.bignum); - return r; - } - - static BigInt product(BigInt a, BigInt b) { - BigInt r = newBigInt(); - NativeBN.BN_mul(r.bignum, a.bignum, b.bignum); - return r; - } - - static BigInt bigExp(BigInt a, BigInt p) { - // Sign of p is ignored! - BigInt r = newBigInt(); - NativeBN.BN_exp(r.bignum, a.bignum, p.bignum); - return r; - } - - static BigInt exp(BigInt a, int p) { - // Sign of p is ignored! - BigInt power = new BigInt(); - power.putLongInt(p); - return bigExp(a, power); - // OPTIONAL: - // int BN_sqr(BigInteger r, BigInteger a, BN_CTX ctx); - // int BN_sqr(BIGNUM *r, const BIGNUM *a,BN_CTX *ctx); - } - - static void division(BigInt dividend, BigInt divisor, BigInt quotient, BigInt remainder) { - long quot, rem; - if (quotient != null) { - quotient.makeValid(); - quot = quotient.bignum; - } else { - quot = 0; - } - if (remainder != null) { - remainder.makeValid(); - rem = remainder.bignum; - } else { - rem = 0; - } - NativeBN.BN_div(quot, rem, dividend.bignum, divisor.bignum); - } - - static BigInt modulus(BigInt a, BigInt m) { - // Sign of p is ignored! ? - BigInt r = newBigInt(); - NativeBN.BN_nnmod(r.bignum, a.bignum, m.bignum); - return r; - } - - static BigInt modExp(BigInt a, BigInt p, BigInt m) { - // Sign of p is ignored! - BigInt r = newBigInt(); - NativeBN.BN_mod_exp(r.bignum, a.bignum, p.bignum, m.bignum); - return r; - } - - - static BigInt modInverse(BigInt a, BigInt m) { - BigInt r = newBigInt(); - NativeBN.BN_mod_inverse(r.bignum, a.bignum, m.bignum); - return r; - } - - - static BigInt generatePrimeDefault(int bitLength) { - BigInt r = newBigInt(); - NativeBN.BN_generate_prime_ex(r.bignum, bitLength, false, 0, 0); - return r; - } - - boolean isPrime(int certainty) { - return NativeBN.BN_primality_test(bignum, certainty, false); - } -} diff --git a/luni/src/main/java/java/math/BigInteger.java b/luni/src/main/java/java/math/BigInteger.java deleted file mode 100644 index b96fdb2f7d..0000000000 --- a/luni/src/main/java/java/math/BigInteger.java +++ /dev/null @@ -1,1275 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package java.math; - -import java.io.IOException; -import java.io.ObjectInputStream; -import java.io.ObjectOutputStream; -import java.io.Serializable; -import java.util.Random; -import libcore.util.NonNull; -import libcore.util.Nullable; - -/** - * An immutable arbitrary-precision signed integer. - * - * <h3>Fast Cryptography</h3> - * This implementation is efficient for operations traditionally used in - * cryptography, such as the generation of large prime numbers and computation - * of the modular inverse. - * - * <h3>Slow Two's Complement Bitwise Operations</h3> - * This API includes operations for bitwise operations in two's complement - * representation. Two's complement is not the internal representation used by - * this implementation, so such methods may be inefficient. Use {@link - * java.util.BitSet} for high-performance bitwise operations on - * arbitrarily-large sequences of bits. - */ -public class BigInteger extends Number - implements Comparable<BigInteger>, Serializable { - - /** This is the serialVersionUID used by the sun implementation. */ - private static final long serialVersionUID = -8287574255936472291L; - - private transient BigInt bigInt; - - private transient boolean nativeIsValid = false; - - private transient boolean javaIsValid = false; - - /** The magnitude of this in the little-endian representation. */ - transient int[] digits; - - /** - * The length of this in measured in ints. Can be less than - * digits.length(). - */ - transient int numberLength; - - /** The sign of this. */ - transient int sign; - - /** The {@code BigInteger} constant 0. */ - @NonNull public static final BigInteger ZERO = new BigInteger(0, 0); - - /** The {@code BigInteger} constant 1. */ - @NonNull public static final BigInteger ONE = new BigInteger(1, 1); - - /** The {@code BigInteger} constant 10. */ - @NonNull public static final BigInteger TEN = new BigInteger(1, 10); - - /** The {@code BigInteger} constant -1. */ - static final BigInteger MINUS_ONE = new BigInteger(-1, 1); - - /** All the {@code BigInteger} numbers in the range [0,10] are cached. */ - static final BigInteger[] SMALL_VALUES = { ZERO, ONE, new BigInteger(1, 2), - new BigInteger(1, 3), new BigInteger(1, 4), new BigInteger(1, 5), - new BigInteger(1, 6), new BigInteger(1, 7), new BigInteger(1, 8), - new BigInteger(1, 9), TEN }; - - private transient int firstNonzeroDigit = -2; - - /** sign field, used for serialization. */ - private int signum; - - /** absolute value field, used for serialization */ - private byte[] magnitude; - - /** Cache for the hash code. */ - private transient int hashCode = 0; - - BigInteger(BigInt bigInt) { - if (bigInt == null || !bigInt.hasNativeBignum()) { - throw new AssertionError(); - } - setBigInt(bigInt); - } - - BigInteger(int sign, long value) { - BigInt bigInt = new BigInt(); - bigInt.putULongInt(value, (sign < 0)); - setBigInt(bigInt); - } - - /** - * Constructs a number without creating new space. This construct should be - * used only if the three fields of representation are known. - * - * @param sign the sign of the number. - * @param numberLength the length of the internal array. - * @param digits a reference of some array created before. - */ - BigInteger(int sign, int numberLength, int[] digits) { - setJavaRepresentation(sign, numberLength, digits); - } - - /** - * Constructs a random non-negative {@code BigInteger} instance in the range - * {@code [0, pow(2, numBits)-1]}. - * - * @param numBits maximum length of the new {@code BigInteger} in bits. - * @param random is the random number generator to be used. - * @throws IllegalArgumentException if {@code numBits} < 0. - */ - public BigInteger(int numBits, @NonNull Random random) { - if (numBits < 0) { - throw new IllegalArgumentException("numBits < 0: " + numBits); - } - if (numBits == 0) { - setJavaRepresentation(0, 1, new int[] { 0 }); - } else { - int sign = 1; - int numberLength = (numBits + 31) >> 5; - int[] digits = new int[numberLength]; - for (int i = 0; i < numberLength; i++) { - digits[i] = random.nextInt(); - } - // Clear any extra bits. - digits[numberLength - 1] >>>= (-numBits) & 31; - setJavaRepresentation(sign, numberLength, digits); - } - javaIsValid = true; - } - - /** - * Constructs a random {@code BigInteger} instance in the range {@code [0, - * pow(2, bitLength)-1]} which is probably prime. The probability that the - * returned {@code BigInteger} is prime is greater than - * {@code 1 - 1/2<sup>certainty</sup>)}. - * - * <p><b>Note:</b> the {@code Random} argument is ignored if - * {@code bitLength >= 16}, where this implementation will use OpenSSL's - * {@code BN_generate_prime_ex} as a source of cryptographically strong pseudo-random numbers. - * - * @param bitLength length of the new {@code BigInteger} in bits. - * @param certainty tolerated primality uncertainty. - * @throws ArithmeticException if {@code bitLength < 2}. - * @see <a href="http://www.openssl.org/docs/crypto/BN_rand.html"> - * Specification of random generator used from OpenSSL library</a> - */ - public BigInteger(int bitLength, int certainty, @NonNull Random random) { - if (bitLength < 2) { - throw new ArithmeticException("bitLength < 2: " + bitLength); - } - if (bitLength < 16) { - // We have to generate short primes ourselves, because OpenSSL bottoms out at 16 bits. - int candidate; - do { - candidate = random.nextInt() & ((1 << bitLength) - 1); - candidate |= (1 << (bitLength - 1)); // Set top bit. - if (bitLength > 2) { - candidate |= 1; // Any prime longer than 2 bits must have the bottom bit set. - } - } while (!isSmallPrime(candidate)); - BigInt prime = new BigInt(); - prime.putULongInt(candidate, false); - setBigInt(prime); - } else { - // We need a loop here to work around an OpenSSL bug; http://b/8588028. - do { - setBigInt(BigInt.generatePrimeDefault(bitLength)); - } while (bitLength() != bitLength); - } - } - - private static boolean isSmallPrime(int x) { - if (x == 2) { - return true; - } - if ((x % 2) == 0) { - return false; - } - final int max = (int) Math.sqrt(x); - for (int i = 3; i <= max; i += 2) { - if ((x % i) == 0) { - return false; - } - } - return true; - } - - /** - * Constructs a new {@code BigInteger} by parsing {@code value}. The string - * representation consists of an optional plus or minus sign followed by a - * non-empty sequence of decimal digits. Digits are interpreted as if by - * {@code Character.digit(char,10)}. - * - * @param value string representation of the new {@code BigInteger}. - * @throws NullPointerException if {@code value == null}. - * @throws NumberFormatException if {@code value} is not a valid - * representation of a {@code BigInteger}. - */ - public BigInteger(@NonNull String value) { - BigInt bigInt = new BigInt(); - bigInt.putDecString(value); - setBigInt(bigInt); - } - - /** - * Constructs a new {@code BigInteger} instance by parsing {@code value}. - * The string representation consists of an optional plus or minus sign - * followed by a non-empty sequence of digits in the specified radix. Digits - * are interpreted as if by {@code Character.digit(char, radix)}. - * - * @param value string representation of the new {@code BigInteger}. - * @param radix the base to be used for the conversion. - * @throws NullPointerException if {@code value == null}. - * @throws NumberFormatException if {@code value} is not a valid - * representation of a {@code BigInteger} or if {@code radix < - * Character.MIN_RADIX} or {@code radix > Character.MAX_RADIX}. - */ - public BigInteger(@NonNull String value, int radix) { - if (value == null) { - throw new NullPointerException("value == null"); - } - if (radix == 10) { - BigInt bigInt = new BigInt(); - bigInt.putDecString(value); - setBigInt(bigInt); - } else if (radix == 16) { - BigInt bigInt = new BigInt(); - bigInt.putHexString(value); - setBigInt(bigInt); - } else { - if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) { - throw new NumberFormatException("Invalid radix: " + radix); - } - if (value.isEmpty()) { - throw new NumberFormatException("value.isEmpty()"); - } - BigInteger.parseFromString(this, value, radix); - } - } - - /** - * Constructs a new {@code BigInteger} instance with the given sign and - * magnitude. - * - * @param signum sign of the new {@code BigInteger} (-1 for negative, 0 for - * zero, 1 for positive). - * @param magnitude magnitude of the new {@code BigInteger} with the most - * significant byte first. - * @throws NullPointerException if {@code magnitude == null}. - * @throws NumberFormatException if the sign is not one of -1, 0, 1 or if - * the sign is zero and the magnitude contains non-zero entries. - */ - public BigInteger(int signum, byte @NonNull [] magnitude) { - if (magnitude == null) { - throw new NullPointerException("magnitude == null"); - } - if (signum < -1 || signum > 1) { - throw new NumberFormatException("Invalid signum: " + signum); - } - if (signum == 0) { - for (byte element : magnitude) { - if (element != 0) { - throw new NumberFormatException("signum-magnitude mismatch"); - } - } - } - BigInt bigInt = new BigInt(); - bigInt.putBigEndian(magnitude, signum < 0); - setBigInt(bigInt); - } - - /** - * Constructs a new {@code BigInteger} from the given two's complement - * representation. The most significant byte is the entry at index 0. The - * most significant bit of this entry determines the sign of the new {@code - * BigInteger} instance. The array must be nonempty. - * - * @param value two's complement representation of the new {@code - * BigInteger}. - * @throws NullPointerException if {@code value == null}. - * @throws NumberFormatException if the length of {@code value} is zero. - */ - public BigInteger(byte @NonNull [] value) { - if (value.length == 0) { - throw new NumberFormatException("value.length == 0"); - } - BigInt bigInt = new BigInt(); - bigInt.putBigEndianTwosComplement(value); - setBigInt(bigInt); - } - - /** - * Returns the internal native representation of this big integer, computing - * it if necessary. - */ - BigInt getBigInt() { - if (nativeIsValid) { - return bigInt; - } - - synchronized (this) { - if (nativeIsValid) { - return bigInt; - } - BigInt bigInt = new BigInt(); - bigInt.putLittleEndianInts(digits, (sign < 0)); - setBigInt(bigInt); - return bigInt; - } - } - - private void setBigInt(BigInt bigInt) { - this.bigInt = bigInt; - this.nativeIsValid = true; - } - - private void setJavaRepresentation(int sign, int numberLength, int[] digits) { - // decrement numberLength to drop leading zeroes... - while (numberLength > 0 && digits[--numberLength] == 0) { - ; - } - // ... and then increment it back because we always drop one too many - if (digits[numberLength++] == 0) { - sign = 0; - } - this.sign = sign; - this.digits = digits; - this.numberLength = numberLength; - this.javaIsValid = true; - } - - void prepareJavaRepresentation() { - if (javaIsValid) { - return; - } - - synchronized (this) { - if (javaIsValid) { - return; - } - int sign = bigInt.sign(); - int[] digits = (sign != 0) ? bigInt.littleEndianIntsMagnitude() : new int[] { 0 }; - setJavaRepresentation(sign, digits.length, digits); - } - } - - /** Returns a {@code BigInteger} whose value is equal to {@code value}. */ - @NonNull public static BigInteger valueOf(long value) { - if (value < 0) { - if (value != -1) { - return new BigInteger(-1, -value); - } - return MINUS_ONE; - } else if (value < SMALL_VALUES.length) { - return SMALL_VALUES[(int) value]; - } else {// (value > 10) - return new BigInteger(1, value); - } - } - - /** - * Returns the two's complement representation of this {@code BigInteger} in - * a byte array. - */ - public byte @NonNull [] toByteArray() { - return twosComplement(); - } - - /** - * Returns a {@code BigInteger} whose value is the absolute value of {@code - * this}. - */ - @NonNull public BigInteger abs() { - BigInt bigInt = getBigInt(); - if (bigInt.sign() >= 0) { - return this; - } - BigInt a = bigInt.copy(); - a.setSign(1); - return new BigInteger(a); - } - - /** - * Returns a {@code BigInteger} whose value is the {@code -this}. - */ - @NonNull public BigInteger negate() { - BigInt bigInt = getBigInt(); - int sign = bigInt.sign(); - if (sign == 0) { - return this; - } - BigInt a = bigInt.copy(); - a.setSign(-sign); - return new BigInteger(a); - } - - /** - * Returns a {@code BigInteger} whose value is {@code this + value}. - */ - @NonNull public BigInteger add(@NonNull BigInteger value) { - BigInt lhs = getBigInt(); - BigInt rhs = value.getBigInt(); - if (rhs.sign() == 0) { - return this; - } - if (lhs.sign() == 0) { - return value; - } - return new BigInteger(BigInt.addition(lhs, rhs)); - } - - /** - * Returns a {@code BigInteger} whose value is {@code this - value}. - */ - @NonNull public BigInteger subtract(@NonNull BigInteger value) { - BigInt lhs = getBigInt(); - BigInt rhs = value.getBigInt(); - if (rhs.sign() == 0) { - return this; - } - return new BigInteger(BigInt.subtraction(lhs, rhs)); - } - - /** - * Returns the sign of this {@code BigInteger}. - * - * @return {@code -1} if {@code this < 0}, {@code 0} if {@code this == 0}, - * {@code 1} if {@code this > 0}. - */ - public int signum() { - if (javaIsValid) { - return sign; - } - return getBigInt().sign(); - } - - /** - * Returns a {@code BigInteger} whose value is {@code this >> n}. For - * negative arguments, the result is also negative. The shift distance may - * be negative which means that {@code this} is shifted left. - * - * <p><b>Implementation Note:</b> Usage of this method on negative values is - * not recommended as the current implementation is not efficient. - * - * @param n shift distance - * @return {@code this >> n} if {@code n >= 0}; {@code this << (-n)} - * otherwise - */ - @NonNull public BigInteger shiftRight(int n) { - return shiftLeft(-n); - } - - /** - * Returns a {@code BigInteger} whose value is {@code this << n}. The - * result is equivalent to {@code this * pow(2, n)} if n >= 0. The shift - * distance may be negative which means that {@code this} is shifted right. - * The result then corresponds to {@code floor(this / pow(2, -n))}. - * - * <p><b>Implementation Note:</b> Usage of this method on negative values is - * not recommended as the current implementation is not efficient. - * - * @param n shift distance. - * @return {@code this << n} if {@code n >= 0}; {@code this >> (-n)}. - * otherwise - */ - @NonNull public BigInteger shiftLeft(int n) { - if (n == 0) { - return this; - } - int sign = signum(); - if (sign == 0) { - return this; - } - if ((sign > 0) || (n >= 0)) { - return new BigInteger(BigInt.shift(getBigInt(), n)); - } else { - // Negative numbers faking 2's complement: - // Not worth optimizing this: - // Sticking to Harmony Java implementation. - return BitLevel.shiftRight(this, -n); - } - } - - BigInteger shiftLeftOneBit() { - return (signum() == 0) ? this : BitLevel.shiftLeftOneBit(this); - } - - /** - * Returns the length of the value's two's complement representation without - * leading zeros for positive numbers / without leading ones for negative - * values. - * - * <p>The two's complement representation of {@code this} will be at least - * {@code bitLength() + 1} bits long. - * - * <p>The value will fit into an {@code int} if {@code bitLength() < 32} or - * into a {@code long} if {@code bitLength() < 64}. - * - * @return the length of the minimal two's complement representation for - * {@code this} without the sign bit. - */ - public int bitLength() { - // Optimization to avoid unnecessary duplicate representation: - if (!nativeIsValid && javaIsValid) { - return BitLevel.bitLength(this); - } - return getBigInt().bitLength(); - } - - /** - * Tests whether the bit at position n in {@code this} is set. The result is - * equivalent to {@code this & pow(2, n) != 0}. - * - * <p><b>Implementation Note:</b> Usage of this method is not recommended as - * the current implementation is not efficient. - * - * @param n position where the bit in {@code this} has to be inspected. - * @throws ArithmeticException if {@code n < 0}. - */ - public boolean testBit(int n) { - if (n < 0) { - throw new ArithmeticException("n < 0: " + n); - } - int sign = signum(); - if (sign > 0 && nativeIsValid && !javaIsValid) { - return getBigInt().isBitSet(n); - } else { - // Negative numbers faking 2's complement: - // Not worth optimizing this: - // Sticking to Harmony Java implementation. - prepareJavaRepresentation(); - if (n == 0) { - return ((digits[0] & 1) != 0); - } - int intCount = n >> 5; - if (intCount >= numberLength) { - return (sign < 0); - } - int digit = digits[intCount]; - n = (1 << (n & 31)); // int with 1 set to the needed position - if (sign < 0) { - int firstNonZeroDigit = getFirstNonzeroDigit(); - if (intCount < firstNonZeroDigit) { - return false; - } else if (firstNonZeroDigit == intCount) { - digit = -digit; - } else { - digit = ~digit; - } - } - return ((digit & n) != 0); - } - } - - /** - * Returns a {@code BigInteger} which has the same binary representation - * as {@code this} but with the bit at position n set. The result is - * equivalent to {@code this | pow(2, n)}. - * - * <p><b>Implementation Note:</b> Usage of this method is not recommended as - * the current implementation is not efficient. - * - * @param n position where the bit in {@code this} has to be set. - * @throws ArithmeticException if {@code n < 0}. - */ - @NonNull public BigInteger setBit(int n) { - prepareJavaRepresentation(); - if (!testBit(n)) { - return BitLevel.flipBit(this, n); - } else { - return this; - } - } - - /** - * Returns a {@code BigInteger} which has the same binary representation - * as {@code this} but with the bit at position n cleared. The result is - * equivalent to {@code this & ~pow(2, n)}. - * - * <p><b>Implementation Note:</b> Usage of this method is not recommended as - * the current implementation is not efficient. - * - * @param n position where the bit in {@code this} has to be cleared. - * @throws ArithmeticException if {@code n < 0}. - */ - @NonNull public BigInteger clearBit(int n) { - prepareJavaRepresentation(); - if (testBit(n)) { - return BitLevel.flipBit(this, n); - } else { - return this; - } - } - - /** - * Returns a {@code BigInteger} which has the same binary representation - * as {@code this} but with the bit at position n flipped. The result is - * equivalent to {@code this ^ pow(2, n)}. - * - * <p><b>Implementation Note:</b> Usage of this method is not recommended as - * the current implementation is not efficient. - * - * @param n position where the bit in {@code this} has to be flipped. - * @throws ArithmeticException if {@code n < 0}. - */ - @NonNull public BigInteger flipBit(int n) { - prepareJavaRepresentation(); - if (n < 0) { - throw new ArithmeticException("n < 0: " + n); - } - return BitLevel.flipBit(this, n); - } - - /** - * Returns the position of the lowest set bit in the two's complement - * representation of this {@code BigInteger}. If all bits are zero (this==0) - * then -1 is returned as result. - * - * <p><b>Implementation Note:</b> Usage of this method is not recommended as - * the current implementation is not efficient. - */ - public int getLowestSetBit() { - prepareJavaRepresentation(); - if (sign == 0) { - return -1; - } - // (sign != 0) implies that exists some non zero digit - int i = getFirstNonzeroDigit(); - return ((i << 5) + Integer.numberOfTrailingZeros(digits[i])); - } - - /** - * Returns the number of bits in the two's complement representation of - * {@code this} which differ from the sign bit. If {@code this} is negative, - * the result is equivalent to the number of bits set in the two's - * complement representation of {@code -this - 1}. - * - * <p>Use {@code bitLength(0)} to find the length of the binary value in - * bits. - * - * <p><b>Implementation Note:</b> Usage of this method is not recommended as - * the current implementation is not efficient. - */ - public int bitCount() { - prepareJavaRepresentation(); - return BitLevel.bitCount(this); - } - - /** - * Returns a {@code BigInteger} whose value is {@code ~this}. The result - * of this operation is {@code -this-1}. - * - * <p><b>Implementation Note:</b> Usage of this method is not recommended as - * the current implementation is not efficient. - */ - @NonNull public BigInteger not() { - this.prepareJavaRepresentation(); - return Logical.not(this); - } - - /** - * Returns a {@code BigInteger} whose value is {@code this & value}. - * - * <p><b>Implementation Note:</b> Usage of this method is not recommended - * as the current implementation is not efficient. - * - * @param value value to be and'ed with {@code this}. - * @throws NullPointerException if {@code value == null}. - */ - @NonNull public BigInteger and(@NonNull BigInteger value) { - this.prepareJavaRepresentation(); - value.prepareJavaRepresentation(); - return Logical.and(this, value); - } - - /** - * Returns a {@code BigInteger} whose value is {@code this | value}. - * - * <p><b>Implementation Note:</b> Usage of this method is not recommended as - * the current implementation is not efficient. - * - * @param value value to be or'ed with {@code this}. - * @throws NullPointerException if {@code value == null}. - */ - @NonNull public BigInteger or(@NonNull BigInteger value) { - this.prepareJavaRepresentation(); - value.prepareJavaRepresentation(); - return Logical.or(this, value); - } - - /** - * Returns a {@code BigInteger} whose value is {@code this ^ value}. - * - * <p><b>Implementation Note:</b> Usage of this method is not recommended as - * the current implementation is not efficient. - * - * @param value value to be xor'ed with {@code this} - * @throws NullPointerException if {@code value == null} - */ - @NonNull public BigInteger xor(@NonNull BigInteger value) { - this.prepareJavaRepresentation(); - value.prepareJavaRepresentation(); - return Logical.xor(this, value); - } - - /** - * Returns a {@code BigInteger} whose value is {@code this & ~value}. - * Evaluating {@code x.andNot(value)} returns the same result as {@code - * x.and(value.not())}. - * - * <p><b>Implementation Note:</b> Usage of this method is not recommended - * as the current implementation is not efficient. - * - * @param value value to be not'ed and then and'ed with {@code this}. - * @throws NullPointerException if {@code value == null}. - */ - @NonNull public BigInteger andNot(@NonNull BigInteger value) { - this.prepareJavaRepresentation(); - value.prepareJavaRepresentation(); - return Logical.andNot(this, value); - } - - /** - * Returns this {@code BigInteger} as an int value. If {@code this} is too - * big to be represented as an int, then {@code this % (1 << 32)} is - * returned. - */ - @Override - public int intValue() { - if (nativeIsValid && bigInt.twosCompFitsIntoBytes(4)) { - return (int) bigInt.longInt(); - } - this.prepareJavaRepresentation(); - return (sign * digits[0]); - } - - /** - * Returns this {@code BigInteger} as a long value. If {@code this} is too - * big to be represented as a long, then {@code this % pow(2, 64)} is - * returned. - */ - @Override - public long longValue() { - if (nativeIsValid && bigInt.twosCompFitsIntoBytes(8)) { - return bigInt.longInt(); - } - prepareJavaRepresentation(); - long value = numberLength > 1 - ? ((long) digits[1]) << 32 | digits[0] & 0xFFFFFFFFL - : digits[0] & 0xFFFFFFFFL; - return sign * value; - } - - /** - * Returns this {@code BigInteger} as a float. If {@code this} is too big to - * be represented as a float, then {@code Float.POSITIVE_INFINITY} or - * {@code Float.NEGATIVE_INFINITY} is returned. Note that not all integers - * in the range {@code [-Float.MAX_VALUE, Float.MAX_VALUE]} can be exactly - * represented as a float. - */ - @Override - public float floatValue() { - return (float) doubleValue(); - } - - /** - * Returns this {@code BigInteger} as a double. If {@code this} is too big - * to be represented as a double, then {@code Double.POSITIVE_INFINITY} or - * {@code Double.NEGATIVE_INFINITY} is returned. Note that not all integers - * in the range {@code [-Double.MAX_VALUE, Double.MAX_VALUE]} can be exactly - * represented as a double. - */ - @Override - public double doubleValue() { - return Conversion.bigInteger2Double(this); - } - - /** - * Compares this {@code BigInteger} with {@code value}. Returns {@code -1} - * if {@code this < value}, {@code 0} if {@code this == value} and {@code 1} - * if {@code this > value}, . - * - * @param value value to be compared with {@code this}. - * @throws NullPointerException if {@code value == null}. - */ - public int compareTo(@NonNull BigInteger value) { - return BigInt.cmp(getBigInt(), value.getBigInt()); - } - - /** - * Returns the minimum of this {@code BigInteger} and {@code value}. - * - * @param value value to be used to compute the minimum with {@code this}. - * @throws NullPointerException if {@code value == null}. - */ - @NonNull public BigInteger min(@NonNull BigInteger value) { - return this.compareTo(value) == -1 ? this : value; - } - - /** - * Returns the maximum of this {@code BigInteger} and {@code value}. - * - * @param value value to be used to compute the maximum with {@code this} - * @throws NullPointerException if {@code value == null} - */ - @NonNull public BigInteger max(@NonNull BigInteger value) { - return this.compareTo(value) == 1 ? this : value; - } - - @Override - public int hashCode() { - if (hashCode == 0) { - prepareJavaRepresentation(); - int hash = 0; - for (int i = 0; i < numberLength; ++i) { - hash = hash * 33 + digits[i]; - } - hashCode = hash * sign; - } - return hashCode; - } - - @Override - public boolean equals(@Nullable Object x) { - if (this == x) { - return true; - } - if (x instanceof BigInteger) { - return this.compareTo((BigInteger) x) == 0; - } - return false; - } - - /** - * Returns a string representation of this {@code BigInteger} in decimal - * form. - */ - @Override - @NonNull public String toString() { - return getBigInt().decString(); - } - - /** - * Returns a string containing a string representation of this {@code - * BigInteger} with base radix. If {@code radix < Character.MIN_RADIX} or - * {@code radix > Character.MAX_RADIX} then a decimal representation is - * returned. The characters of the string representation are generated with - * method {@code Character.forDigit}. - * - * @param radix base to be used for the string representation. - */ - @NonNull public String toString(int radix) { - if (radix == 10) { - return getBigInt().decString(); - } else { - prepareJavaRepresentation(); - return Conversion.bigInteger2String(this, radix); - } - } - - /** - * Returns a {@code BigInteger} whose value is greatest common divisor - * of {@code this} and {@code value}. If {@code this == 0} and {@code - * value == 0} then zero is returned, otherwise the result is positive. - * - * @param value value with which the greatest common divisor is computed. - * @throws NullPointerException if {@code value == null}. - */ - @NonNull public BigInteger gcd(@NonNull BigInteger value) { - // First optimize the case in which the two arguments have very different - // length. - int thisLen = bitLength(); - int valueLen = value.bitLength(); - final int gcdDirectRatio = 16; - if (thisLen > gcdDirectRatio * valueLen) { - // A division-based step reduces the length of this by a factor of at - // least gcdDirectRatio, thus ensuring that a division-based step will - // easily pay for itself. - if (value.signum() == 0) { - return this.abs(); - } - return value.gcd(this.mod(value.abs())); - } else if (valueLen > gcdDirectRatio * thisLen) { - if (signum() == 0) { - return value.abs(); - } - return this.gcd(value.mod(this.abs())); - } - - return new BigInteger(BigInt.gcd(getBigInt(), value.getBigInt())); - } - - /** - * Returns a {@code BigInteger} whose value is {@code this * value}. - * - * @throws NullPointerException if {@code value == null}. - */ - @NonNull public BigInteger multiply(@NonNull BigInteger value) { - return new BigInteger(BigInt.product(getBigInt(), value.getBigInt())); - } - - /** - * Returns a {@code BigInteger} whose value is {@code pow(this, exp)}. - * - * @throws ArithmeticException if {@code exp < 0}. - */ - @NonNull public BigInteger pow(int exp) { - if (exp < 0) { - throw new ArithmeticException("exp < 0: " + exp); - } - return new BigInteger(BigInt.exp(getBigInt(), exp)); - } - - /** - * Returns a two element {@code BigInteger} array containing - * {@code this / divisor} at index 0 and {@code this % divisor} at index 1. - * - * @param divisor value by which {@code this} is divided. - * @throws NullPointerException if {@code divisor == null}. - * @throws ArithmeticException if {@code divisor == 0}. - * @see #divide - * @see #remainder - */ - public @NonNull BigInteger @NonNull [] divideAndRemainder(@NonNull BigInteger divisor) { - BigInt divisorBigInt = divisor.getBigInt(); - BigInt quotient = new BigInt(); - BigInt remainder = new BigInt(); - BigInt.division(getBigInt(), divisorBigInt, quotient, remainder); - return new BigInteger[] {new BigInteger(quotient), new BigInteger(remainder) }; - } - - /** - * Returns a {@code BigInteger} whose value is {@code this / divisor}. - * - * @param divisor value by which {@code this} is divided. - * @return {@code this / divisor}. - * @throws NullPointerException if {@code divisor == null}. - * @throws ArithmeticException if {@code divisor == 0}. - */ - @NonNull public BigInteger divide(@NonNull BigInteger divisor) { - BigInt quotient = new BigInt(); - BigInt.division(getBigInt(), divisor.getBigInt(), quotient, null); - return new BigInteger(quotient); - } - - /** - * Returns a {@code BigInteger} whose value is {@code this % divisor}. - * Regarding signs this methods has the same behavior as the % operator on - * ints: the sign of the remainder is the same as the sign of this. - * - * @param divisor value by which {@code this} is divided. - * @throws NullPointerException if {@code divisor == null}. - * @throws ArithmeticException if {@code divisor == 0}. - */ - @NonNull public BigInteger remainder(@NonNull BigInteger divisor) { - BigInt remainder = new BigInt(); - BigInt.division(getBigInt(), divisor.getBigInt(), null, remainder); - return new BigInteger(remainder); - } - - /** - * Returns a {@code BigInteger} whose value is {@code 1/this mod m}. The - * modulus {@code m} must be positive. The result is guaranteed to be in the - * interval {@code [0, m)} (0 inclusive, m exclusive). If {@code this} is - * not relatively prime to m, then an exception is thrown. - * - * @param m the modulus. - * @throws NullPointerException if {@code m == null} - * @throws ArithmeticException if {@code m < 0 or} if {@code this} is not - * relatively prime to {@code m} - */ - @NonNull public BigInteger modInverse(@NonNull BigInteger m) { - if (m.signum() <= 0) { - throw new ArithmeticException("modulus not positive"); - } - return new BigInteger(BigInt.modInverse(getBigInt(), m.getBigInt())); - } - - /** - * Returns a {@code BigInteger} whose value is {@code - * pow(this, exponent) mod modulus}. The modulus must be positive. The - * result is guaranteed to be in the interval {@code [0, modulus)}. - * If the exponent is negative, then - * {@code pow(this.modInverse(modulus), -exponent) mod modulus} is computed. - * The inverse of this only exists if {@code this} is relatively prime to the modulus, - * otherwise an exception is thrown. - * - * @throws NullPointerException if {@code modulus == null} or {@code exponent == null}. - * @throws ArithmeticException if {@code modulus < 0} or if {@code exponent < 0} and - * not relatively prime to {@code modulus}. - */ - @NonNull public BigInteger modPow(@NonNull BigInteger exponent, @NonNull BigInteger modulus) { - if (modulus.signum() <= 0) { - throw new ArithmeticException("modulus.signum() <= 0"); - } - int exponentSignum = exponent.signum(); - if (exponentSignum == 0) { // OpenSSL gets this case wrong; http://b/8574367. - return ONE.mod(modulus); - } - BigInteger base = exponentSignum < 0 ? modInverse(modulus) : this; - return new BigInteger(BigInt.modExp(base.getBigInt(), exponent.getBigInt(), modulus.getBigInt())); - } - - /** - * Returns a {@code BigInteger} whose value is {@code this mod m}. The - * modulus {@code m} must be positive. The result is guaranteed to be in the - * interval {@code [0, m)} (0 inclusive, m exclusive). The behavior of this - * function is not equivalent to the behavior of the % operator defined for - * the built-in {@code int}'s. - * - * @param m the modulus. - * @return {@code this mod m}. - * @throws NullPointerException if {@code m == null}. - * @throws ArithmeticException if {@code m < 0}. - */ - @NonNull public BigInteger mod(@NonNull BigInteger m) { - if (m.signum() <= 0) { - throw new ArithmeticException("m.signum() <= 0"); - } - return new BigInteger(BigInt.modulus(getBigInt(), m.getBigInt())); - } - - /** - * Tests whether this {@code BigInteger} is probably prime. If {@code true} - * is returned, then this is prime with a probability greater than - * {@code 1 - 1/2<sup>certainty</sup>)}. If {@code false} is returned, then this - * is definitely composite. If the argument {@code certainty} <= 0, then - * this method returns true. - * - * @param certainty tolerated primality uncertainty. - * @return {@code true}, if {@code this} is probably prime, {@code false} - * otherwise. - */ - public boolean isProbablePrime(int certainty) { - if (certainty <= 0) { - return true; - } - return getBigInt().isPrime(certainty); - } - - /** - * Returns the smallest integer x > {@code this} which is probably prime as - * a {@code BigInteger} instance. The probability that the returned {@code - * BigInteger} is prime is greater than {@code 1 - 1/2<sup>100</sup>}. - * - * @return smallest integer > {@code this} which is probably prime. - * @throws ArithmeticException if {@code this < 0}. - */ - @NonNull public BigInteger nextProbablePrime() { - if (sign < 0) { - throw new ArithmeticException("sign < 0"); - } - return Primality.nextProbablePrime(this); - } - - /** - * Returns a random positive {@code BigInteger} instance in the range {@code - * [0, pow(2, bitLength)-1]} which is probably prime. The probability that - * the returned {@code BigInteger} is prime is greater than {@code 1 - 1/2<sup>100</sup>)}. - * - * @param bitLength length of the new {@code BigInteger} in bits. - * @return probably prime random {@code BigInteger} instance. - * @throws IllegalArgumentException if {@code bitLength < 2}. - */ - @NonNull public static BigInteger probablePrime(int bitLength, @NonNull Random random) { - return new BigInteger(bitLength, 100, random); - } - - /* Private Methods */ - - /** - * Returns the two's complement representation of this BigInteger in a byte - * array. - */ - private byte[] twosComplement() { - prepareJavaRepresentation(); - if (this.sign == 0) { - return new byte[] { 0 }; - } - BigInteger temp = this; - int bitLen = bitLength(); - int iThis = getFirstNonzeroDigit(); - int bytesLen = (bitLen >> 3) + 1; - /* Puts the little-endian int array representing the magnitude - * of this BigInteger into the big-endian byte array. */ - byte[] bytes = new byte[bytesLen]; - int firstByteNumber = 0; - int highBytes; - int bytesInInteger = 4; - int hB; - - if (bytesLen - (numberLength << 2) == 1) { - bytes[0] = (byte) ((sign < 0) ? -1 : 0); - highBytes = 4; - firstByteNumber++; - } else { - hB = bytesLen & 3; - highBytes = (hB == 0) ? 4 : hB; - } - - int digitIndex = iThis; - bytesLen -= iThis << 2; - - if (sign < 0) { - int digit = -temp.digits[digitIndex]; - digitIndex++; - if (digitIndex == numberLength) { - bytesInInteger = highBytes; - } - for (int i = 0; i < bytesInInteger; i++, digit >>= 8) { - bytes[--bytesLen] = (byte) digit; - } - while (bytesLen > firstByteNumber) { - digit = ~temp.digits[digitIndex]; - digitIndex++; - if (digitIndex == numberLength) { - bytesInInteger = highBytes; - } - for (int i = 0; i < bytesInInteger; i++, digit >>= 8) { - bytes[--bytesLen] = (byte) digit; - } - } - } else { - while (bytesLen > firstByteNumber) { - int digit = temp.digits[digitIndex]; - digitIndex++; - if (digitIndex == numberLength) { - bytesInInteger = highBytes; - } - for (int i = 0; i < bytesInInteger; i++, digit >>= 8) { - bytes[--bytesLen] = (byte) digit; - } - } - } - return bytes; - } - - - static int multiplyByInt(int[] res, int[] a, int aSize, int factor) { - long carry = 0; - - for (int i = 0; i < aSize; i++) { - carry += (a[i] & 0xFFFFFFFFL) * (factor & 0xFFFFFFFFL); - res[i] = (int) carry; - carry >>>= 32; - } - return (int) carry; - } - - static int inplaceAdd(int[] a, int aSize, int addend) { - long carry = addend & 0xFFFFFFFFL; - - for (int i = 0; (carry != 0) && (i < aSize); i++) { - carry += a[i] & 0xFFFFFFFFL; - a[i] = (int) carry; - carry >>= 32; - } - return (int) carry; - } - - /** @see BigInteger#BigInteger(String, int) */ - private static void parseFromString(BigInteger bi, String value, int radix) { - int stringLength = value.length(); - int endChar = stringLength; - - int sign; - int startChar; - if (value.charAt(0) == '-') { - sign = -1; - startChar = 1; - stringLength--; - } else { - sign = 1; - startChar = 0; - } - - /* - * We use the following algorithm: split a string into portions of n - * characters and convert each portion to an integer according to the - * radix. Then convert an pow(radix, n) based number to binary using the - * multiplication method. See D. Knuth, The Art of Computer Programming, - * vol. 2. - */ - - int charsPerInt = Conversion.digitFitInInt[radix]; - int bigRadixDigitsLength = stringLength / charsPerInt; - int topChars = stringLength % charsPerInt; - - if (topChars != 0) { - bigRadixDigitsLength++; - } - int[] digits = new int[bigRadixDigitsLength]; - // Get the maximal power of radix that fits in int - int bigRadix = Conversion.bigRadices[radix - 2]; - // Parse an input string and accumulate the BigInteger's magnitude - int digitIndex = 0; // index of digits array - int substrEnd = startChar + ((topChars == 0) ? charsPerInt : topChars); - - for (int substrStart = startChar; substrStart < endChar; - substrStart = substrEnd, substrEnd = substrStart + charsPerInt) { - int bigRadixDigit = Integer.parseInt(value.substring(substrStart, substrEnd), radix); - int newDigit = multiplyByInt(digits, digits, digitIndex, bigRadix); - newDigit += inplaceAdd(digits, digitIndex, bigRadixDigit); - digits[digitIndex++] = newDigit; - } - int numberLength = digitIndex; - bi.setJavaRepresentation(sign, numberLength, digits); - } - - int getFirstNonzeroDigit() { - if (firstNonzeroDigit == -2) { - int i; - if (this.sign == 0) { - i = -1; - } else { - for (i = 0; digits[i] == 0; i++) { - ; - } - } - firstNonzeroDigit = i; - } - return firstNonzeroDigit; - } - - /** - * Returns a copy of the current instance to achieve immutability - */ - BigInteger copy() { - prepareJavaRepresentation(); - int[] copyDigits = new int[numberLength]; - System.arraycopy(digits, 0, copyDigits, 0, numberLength); - return new BigInteger(sign, numberLength, copyDigits); - } - - /** - * Assigns all transient fields upon deserialization of a {@code BigInteger} - * instance. - */ - private void readObject(ObjectInputStream in) - throws IOException, ClassNotFoundException { - in.defaultReadObject(); - BigInt bigInt = new BigInt(); - bigInt.putBigEndian(magnitude, signum < 0); - setBigInt(bigInt); - } - - /** - * Prepares this {@code BigInteger} for serialization, i.e. the - * non-transient fields {@code signum} and {@code magnitude} are assigned. - */ - private void writeObject(ObjectOutputStream out) throws IOException { - BigInt bigInt = getBigInt(); - signum = bigInt.sign(); - magnitude = bigInt.bigEndianMagnitude(); - out.defaultWriteObject(); - } -} diff --git a/luni/src/main/java/java/math/BitLevel.java b/luni/src/main/java/java/math/BitLevel.java deleted file mode 100644 index 91f7a9b283..0000000000 --- a/luni/src/main/java/java/math/BitLevel.java +++ /dev/null @@ -1,255 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package java.math; - -/** - * Static library that provides all the <b>bit level</b> operations for - * {@link BigInteger}. The operations are: - * <ul type="circle"> - * <li>Left Shifting</li> - * <li>Right Shifting</li> - * <li>Bit clearing</li> - * <li>Bit setting</li> - * <li>Bit counting</li> - * <li>Bit testing</li> - * <li>Getting of the lowest bit set</li> - * </ul> - * All operations are provided in immutable way, and some in both mutable and - * immutable. - */ -class BitLevel { - - /** Just to denote that this class can't be instantiated. */ - private BitLevel() {} - - /** @see BigInteger#bitLength() */ - static int bitLength(BigInteger val) { - val.prepareJavaRepresentation(); - if (val.sign == 0) { - return 0; - } - int bLength = (val.numberLength << 5); - int highDigit = val.digits[val.numberLength - 1]; - - if (val.sign < 0) { - int i = val.getFirstNonzeroDigit(); - // We reduce the problem to the positive case. - if (i == val.numberLength - 1) { - highDigit--; - } - } - // Subtracting all sign bits - bLength -= Integer.numberOfLeadingZeros(highDigit); - return bLength; - } - - /** @see BigInteger#bitCount() */ - static int bitCount(BigInteger val) { - val.prepareJavaRepresentation(); - int bCount = 0; - - if (val.sign == 0) { - return 0; - } - - int i = val.getFirstNonzeroDigit(); - if (val.sign > 0) { - for ( ; i < val.numberLength; i++) { - bCount += Integer.bitCount(val.digits[i]); - } - } else {// (sign < 0) - // this digit absorbs the carry - bCount += Integer.bitCount(-val.digits[i]); - for (i++; i < val.numberLength; i++) { - bCount += Integer.bitCount(~val.digits[i]); - } - // We take the complement sum: - bCount = (val.numberLength << 5) - bCount; - } - return bCount; - } - - /** - * Performs a fast bit testing for positive numbers. The bit to to be tested - * must be in the range {@code [0, val.bitLength()-1]} - */ - static boolean testBit(BigInteger val, int n) { - val.prepareJavaRepresentation(); - // PRE: 0 <= n < val.bitLength() - return ((val.digits[n >> 5] & (1 << (n & 31))) != 0); - } - - /** - * Check if there are 1s in the lowest bits of this BigInteger - * - * @param numberOfBits the number of the lowest bits to check - * @return false if all bits are 0s, true otherwise - */ - static boolean nonZeroDroppedBits(int numberOfBits, int[] digits) { - int intCount = numberOfBits >> 5; - int bitCount = numberOfBits & 31; - int i; - - for (i = 0; (i < intCount) && (digits[i] == 0); i++) { - ; - } - return ((i != intCount) || (digits[i] << (32 - bitCount) != 0)); - } - - static void shiftLeftOneBit(int[] result, int[] source, int srcLen) { - int carry = 0; - for (int i = 0; i < srcLen; i++) { - int val = source[i]; - result[i] = (val << 1) | carry; - carry = val >>> 31; - } - if(carry != 0) { - result[srcLen] = carry; - } - } - - static BigInteger shiftLeftOneBit(BigInteger source) { - source.prepareJavaRepresentation(); - int srcLen = source.numberLength; - int resLen = srcLen + 1; - int[] resDigits = new int[resLen]; - shiftLeftOneBit(resDigits, source.digits, srcLen); - return new BigInteger(source.sign, resLen, resDigits); - } - - /** @see BigInteger#shiftRight(int) */ - static BigInteger shiftRight(BigInteger source, int count) { - source.prepareJavaRepresentation(); - int intCount = count >> 5; // count of integers - count &= 31; // count of remaining bits - if (intCount >= source.numberLength) { - return ((source.sign < 0) ? BigInteger.MINUS_ONE : BigInteger.ZERO); - } - int i; - int resLength = source.numberLength - intCount; - int[] resDigits = new int[resLength + 1]; - - shiftRight(resDigits, resLength, source.digits, intCount, count); - if (source.sign < 0) { - // Checking if the dropped bits are zeros (the remainder equals to - // 0) - for (i = 0; (i < intCount) && (source.digits[i] == 0); i++) { - ; - } - // If the remainder is not zero, add 1 to the result - if ((i < intCount) - || ((count > 0) && ((source.digits[i] << (32 - count)) != 0))) { - for (i = 0; (i < resLength) && (resDigits[i] == -1); i++) { - resDigits[i] = 0; - } - if (i == resLength) { - resLength++; - } - resDigits[i]++; - } - } - return new BigInteger(source.sign, resLength, resDigits); - } - - /** - * Shifts right an array of integers. Total shift distance in bits is - * intCount * 32 + count. - * - * @param result - * the destination array - * @param resultLen - * the destination array's length - * @param source - * the source array - * @param intCount - * the number of elements to be shifted - * @param count - * the number of bits to be shifted - * @return dropped bit's are all zero (i.e. remaider is zero) - */ - static boolean shiftRight(int[] result, int resultLen, int[] source, int intCount, int count) { - int i; - boolean allZero = true; - for (i = 0; i < intCount; i++) - allZero &= source[i] == 0; - if (count == 0) { - System.arraycopy(source, intCount, result, 0, resultLen); - i = resultLen; - } else { - int leftShiftCount = 32 - count; - - allZero &= ( source[i] << leftShiftCount ) == 0; - for (i = 0; i < resultLen - 1; i++) { - result[i] = ( source[i + intCount] >>> count ) - | ( source[i + intCount + 1] << leftShiftCount ); - } - result[i] = ( source[i + intCount] >>> count ); - i++; - } - - return allZero; - } - - - /** - * Performs a flipBit on the BigInteger, returning a BigInteger with the the - * specified bit flipped. - */ - static BigInteger flipBit(BigInteger val, int n){ - val.prepareJavaRepresentation(); - int resSign = (val.sign == 0) ? 1 : val.sign; - int intCount = n >> 5; - int bitN = n & 31; - int resLength = Math.max(intCount + 1, val.numberLength) + 1; - int[] resDigits = new int[resLength]; - int i; - - int bitNumber = 1 << bitN; - System.arraycopy(val.digits, 0, resDigits, 0, val.numberLength); - - if (val.sign < 0) { - if (intCount >= val.numberLength) { - resDigits[intCount] = bitNumber; - } else { - //val.sign<0 y intCount < val.numberLength - int firstNonZeroDigit = val.getFirstNonzeroDigit(); - if (intCount > firstNonZeroDigit) { - resDigits[intCount] ^= bitNumber; - } else if (intCount < firstNonZeroDigit) { - resDigits[intCount] = -bitNumber; - for (i=intCount + 1; i < firstNonZeroDigit; i++) { - resDigits[i]=-1; - } - resDigits[i] = resDigits[i]--; - } else { - i = intCount; - resDigits[i] = -((-resDigits[intCount]) ^ bitNumber); - if (resDigits[i] == 0) { - for (i++; resDigits[i] == -1 ; i++) { - resDigits[i] = 0; - } - resDigits[i]++; - } - } - } - } else {//case where val is positive - resDigits[intCount] ^= bitNumber; - } - return new BigInteger(resSign, resLength, resDigits); - } -} diff --git a/luni/src/main/java/java/math/Conversion.java b/luni/src/main/java/java/math/Conversion.java deleted file mode 100644 index 585fff43c2..0000000000 --- a/luni/src/main/java/java/math/Conversion.java +++ /dev/null @@ -1,461 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package java.math; - -/** - * Static library that provides {@link BigInteger} base conversion from/to any - * integer represented in an {@link java.lang.String} Object. - */ -class Conversion { - - /** Just to denote that this class can't be instantiated */ - private Conversion() {} - - /** - * Holds the maximal exponent for each radix, so that radix<sup>digitFitInInt[radix]</sup> - * fit in an {@code int} (32 bits). - */ - static final int[] digitFitInInt = { -1, -1, 31, 19, 15, 13, 11, - 11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, - 6, 6, 6, 6, 6, 6, 6, 5 }; - - /** - * bigRadices values are precomputed maximal powers of radices (integer - * numbers from 2 to 36) that fit into unsigned int (32 bits). bigRadices[0] = - * 2 ^ 31, bigRadices[8] = 10 ^ 9, etc. - */ - - static final int[] bigRadices = { -2147483648, 1162261467, - 1073741824, 1220703125, 362797056, 1977326743, 1073741824, - 387420489, 1000000000, 214358881, 429981696, 815730721, 1475789056, - 170859375, 268435456, 410338673, 612220032, 893871739, 1280000000, - 1801088541, 113379904, 148035889, 191102976, 244140625, 308915776, - 387420489, 481890304, 594823321, 729000000, 887503681, 1073741824, - 1291467969, 1544804416, 1838265625, 60466176 }; - - - /** @see BigInteger#toString(int) */ - static String bigInteger2String(BigInteger val, int radix) { - val.prepareJavaRepresentation(); - int sign = val.sign; - int numberLength = val.numberLength; - int[] digits = val.digits; - - if (sign == 0) { - return "0"; - } - if (numberLength == 1) { - int highDigit = digits[numberLength - 1]; - long v = highDigit & 0xFFFFFFFFL; - if (sign < 0) { - v = -v; - } - return Long.toString(v, radix); - } - if ((radix == 10) || (radix < Character.MIN_RADIX) - || (radix > Character.MAX_RADIX)) { - return val.toString(); - } - double bitsForRadixDigit; - bitsForRadixDigit = Math.log(radix) / Math.log(2); - int resLengthInChars = (int) (val.abs().bitLength() / bitsForRadixDigit + ((sign < 0) ? 1 - : 0)) + 1; - - char[] result = new char[resLengthInChars]; - int currentChar = resLengthInChars; - int resDigit; - if (radix != 16) { - int[] temp = new int[numberLength]; - System.arraycopy(digits, 0, temp, 0, numberLength); - int tempLen = numberLength; - int charsPerInt = digitFitInInt[radix]; - int i; - // get the maximal power of radix that fits in int - int bigRadix = bigRadices[radix - 2]; - while (true) { - // divide the array of digits by bigRadix and convert remainders - // to characters collecting them in the char array - resDigit = Division.divideArrayByInt(temp, temp, tempLen, - bigRadix); - int previous = currentChar; - do { - result[--currentChar] = Character.forDigit( - resDigit % radix, radix); - } while (((resDigit /= radix) != 0) && (currentChar != 0)); - int delta = charsPerInt - previous + currentChar; - for (i = 0; i < delta && currentChar > 0; i++) { - result[--currentChar] = '0'; - } - for (i = tempLen - 1; (i > 0) && (temp[i] == 0); i--) { - ; - } - tempLen = i + 1; - if ((tempLen == 1) && (temp[0] == 0)) { // the quotient is 0 - break; - } - } - } else { - // radix == 16 - for (int i = 0; i < numberLength; i++) { - for (int j = 0; (j < 8) && (currentChar > 0); j++) { - resDigit = digits[i] >> (j << 2) & 0xf; - result[--currentChar] = Character.forDigit(resDigit, 16); - } - } - } - while (result[currentChar] == '0') { - currentChar++; - } - if (sign == -1) { - result[--currentChar] = '-'; - } - return new String(result, currentChar, resLengthInChars - currentChar); - } - - /** - * Builds the correspondent {@code String} representation of {@code val} - * being scaled by {@code scale}. - * - * @see BigInteger#toString() - * @see BigDecimal#toString() - */ - static String toDecimalScaledString(BigInteger val, int scale) { - val.prepareJavaRepresentation(); - int sign = val.sign; - int numberLength = val.numberLength; - int[] digits = val.digits; - int resLengthInChars; - int currentChar; - char[] result; - - if (sign == 0) { - switch (scale) { - case 0: - return "0"; - case 1: - return "0.0"; - case 2: - return "0.00"; - case 3: - return "0.000"; - case 4: - return "0.0000"; - case 5: - return "0.00000"; - case 6: - return "0.000000"; - default: - StringBuilder result1 = new StringBuilder(); - if (scale < 0) { - result1.append("0E+"); - } else { - result1.append("0E"); - } - result1.append(-scale); - return result1.toString(); - } - } - // one 32-bit unsigned value may contains 10 decimal digits - resLengthInChars = numberLength * 10 + 1 + 7; - // Explanation why +1+7: - // +1 - one char for sign if needed. - // +7 - For "special case 2" (see below) we have 7 free chars for - // inserting necessary scaled digits. - result = new char[resLengthInChars + 1]; - // allocated [resLengthInChars+1] characters. - // a free latest character may be used for "special case 1" (see - // below) - currentChar = resLengthInChars; - if (numberLength == 1) { - int highDigit = digits[0]; - if (highDigit < 0) { - long v = highDigit & 0xFFFFFFFFL; - do { - long prev = v; - v /= 10; - result[--currentChar] = (char) (0x0030 + ((int) (prev - v * 10))); - } while (v != 0); - } else { - int v = highDigit; - do { - int prev = v; - v /= 10; - result[--currentChar] = (char) (0x0030 + (prev - v * 10)); - } while (v != 0); - } - } else { - int[] temp = new int[numberLength]; - int tempLen = numberLength; - System.arraycopy(digits, 0, temp, 0, tempLen); - BIG_LOOP: while (true) { - // divide the array of digits by bigRadix and convert - // remainders - // to characters collecting them in the char array - long result11 = 0; - for (int i1 = tempLen - 1; i1 >= 0; i1--) { - long temp1 = (result11 << 32) - + (temp[i1] & 0xFFFFFFFFL); - long res = divideLongByBillion(temp1); - temp[i1] = (int) res; - result11 = (int) (res >> 32); - } - int resDigit = (int) result11; - int previous = currentChar; - do { - result[--currentChar] = (char) (0x0030 + (resDigit % 10)); - } while (((resDigit /= 10) != 0) && (currentChar != 0)); - int delta = 9 - previous + currentChar; - for (int i = 0; (i < delta) && (currentChar > 0); i++) { - result[--currentChar] = '0'; - } - int j = tempLen - 1; - for (; temp[j] == 0; j--) { - if (j == 0) { // means temp[0] == 0 - break BIG_LOOP; - } - } - tempLen = j + 1; - } - while (result[currentChar] == '0') { - currentChar++; - } - } - boolean negNumber = (sign < 0); - int exponent = resLengthInChars - currentChar - scale - 1; - if (scale == 0) { - if (negNumber) { - result[--currentChar] = '-'; - } - return new String(result, currentChar, resLengthInChars - - currentChar); - } - if ((scale > 0) && (exponent >= -6)) { - if (exponent >= 0) { - // special case 1 - int insertPoint = currentChar + exponent; - for (int j = resLengthInChars - 1; j >= insertPoint; j--) { - result[j + 1] = result[j]; - } - result[++insertPoint] = '.'; - if (negNumber) { - result[--currentChar] = '-'; - } - return new String(result, currentChar, resLengthInChars - - currentChar + 1); - } - // special case 2 - for (int j = 2; j < -exponent + 1; j++) { - result[--currentChar] = '0'; - } - result[--currentChar] = '.'; - result[--currentChar] = '0'; - if (negNumber) { - result[--currentChar] = '-'; - } - return new String(result, currentChar, resLengthInChars - - currentChar); - } - int startPoint = currentChar + 1; - int endPoint = resLengthInChars; - StringBuilder result1 = new StringBuilder(16 + endPoint - startPoint); - if (negNumber) { - result1.append('-'); - } - if (endPoint - startPoint >= 1) { - result1.append(result[currentChar]); - result1.append('.'); - result1.append(result, currentChar + 1, resLengthInChars - - currentChar - 1); - } else { - result1.append(result, currentChar, resLengthInChars - - currentChar); - } - result1.append('E'); - if (exponent > 0) { - result1.append('+'); - } - result1.append(Integer.toString(exponent)); - return result1.toString(); - } - - /* can process only 32-bit numbers */ - static String toDecimalScaledString(long value, int scale) { - int resLengthInChars; - int currentChar; - char[] result; - boolean negNumber = value < 0; - if(negNumber) { - value = -value; - } - if (value == 0) { - switch (scale) { - case 0: return "0"; - case 1: return "0.0"; - case 2: return "0.00"; - case 3: return "0.000"; - case 4: return "0.0000"; - case 5: return "0.00000"; - case 6: return "0.000000"; - default: - StringBuilder result1 = new StringBuilder(); - if (scale < 0) { - result1.append("0E+"); - } else { - result1.append("0E"); - } - result1.append( (scale == Integer.MIN_VALUE) ? "2147483648" : Integer.toString(-scale)); - return result1.toString(); - } - } - // one 32-bit unsigned value may contains 10 decimal digits - resLengthInChars = 18; - // Explanation why +1+7: - // +1 - one char for sign if needed. - // +7 - For "special case 2" (see below) we have 7 free chars for - // inserting necessary scaled digits. - result = new char[resLengthInChars+1]; - // Allocated [resLengthInChars+1] characters. - // a free latest character may be used for "special case 1" (see below) - currentChar = resLengthInChars; - long v = value; - do { - long prev = v; - v /= 10; - result[--currentChar] = (char) (0x0030 + (prev - v * 10)); - } while (v != 0); - - long exponent = (long)resLengthInChars - (long)currentChar - scale - 1L; - if (scale == 0) { - if (negNumber) { - result[--currentChar] = '-'; - } - return new String(result, currentChar, resLengthInChars - currentChar); - } - if (scale > 0 && exponent >= -6) { - if (exponent >= 0) { - // special case 1 - int insertPoint = currentChar + (int) exponent ; - for (int j=resLengthInChars-1; j>=insertPoint; j--) { - result[j+1] = result[j]; - } - result[++insertPoint]='.'; - if (negNumber) { - result[--currentChar] = '-'; - } - return new String(result, currentChar, resLengthInChars - currentChar + 1); - } - // special case 2 - for (int j = 2; j < -exponent + 1; j++) { - result[--currentChar] = '0'; - } - result[--currentChar] = '.'; - result[--currentChar] = '0'; - if (negNumber) { - result[--currentChar] = '-'; - } - return new String(result, currentChar, resLengthInChars - currentChar); - } - int startPoint = currentChar + 1; - int endPoint = resLengthInChars; - StringBuilder result1 = new StringBuilder(16 + endPoint - startPoint); - if (negNumber) { - result1.append('-'); - } - if (endPoint - startPoint >= 1) { - result1.append(result[currentChar]); - result1.append('.'); - result1.append(result,currentChar+1,resLengthInChars - currentChar-1); - } else { - result1.append(result,currentChar,resLengthInChars - currentChar); - } - result1.append('E'); - if (exponent > 0) { - result1.append('+'); - } - result1.append(Long.toString(exponent)); - return result1.toString(); - } - - static long divideLongByBillion(long a) { - long quot; - long rem; - - if (a >= 0) { - long bLong = 1000000000L; - quot = (a / bLong); - rem = (a % bLong); - } else { - /* - * Make the dividend positive shifting it right by 1 bit then get - * the quotient an remainder and correct them properly - */ - long aPos = a >>> 1; - long bPos = 1000000000L >>> 1; - quot = aPos / bPos; - rem = aPos % bPos; - // double the remainder and add 1 if 'a' is odd - rem = (rem << 1) + (a & 1); - } - return ((rem << 32) | (quot & 0xFFFFFFFFL)); - } - - /** @see BigInteger#doubleValue() */ - static double bigInteger2Double(BigInteger val) { - val.prepareJavaRepresentation(); - // val.bitLength() < 64 - if ((val.numberLength < 2) - || ((val.numberLength == 2) && (val.digits[1] > 0))) { - return val.longValue(); - } - // val.bitLength() >= 33 * 32 > 1024 - if (val.numberLength > 32) { - return ((val.sign > 0) ? Double.POSITIVE_INFINITY - : Double.NEGATIVE_INFINITY); - } - int bitLen = val.abs().bitLength(); - long exponent = bitLen - 1; - int delta = bitLen - 54; - // We need 54 top bits from this, the 53th bit is always 1 in lVal. - long lVal = val.abs().shiftRight(delta).longValue(); - /* - * Take 53 bits from lVal to mantissa. The least significant bit is - * needed for rounding. - */ - long mantissa = lVal & 0x1FFFFFFFFFFFFFL; - if (exponent == 1023) { - if (mantissa == 0X1FFFFFFFFFFFFFL) { - return ((val.sign > 0) ? Double.POSITIVE_INFINITY - : Double.NEGATIVE_INFINITY); - } - if (mantissa == 0x1FFFFFFFFFFFFEL) { - return ((val.sign > 0) ? Double.MAX_VALUE : -Double.MAX_VALUE); - } - } - // Round the mantissa - if (((mantissa & 1) == 1) - && (((mantissa & 2) == 2) || BitLevel.nonZeroDroppedBits(delta, - val.digits))) { - mantissa += 2; - } - mantissa >>= 1; // drop the rounding bit - long resSign = (val.sign < 0) ? 0x8000000000000000L : 0; - exponent = ((1023 + exponent) << 52) & 0x7FF0000000000000L; - long result = resSign | exponent | mantissa; - return Double.longBitsToDouble(result); - } -} diff --git a/luni/src/main/java/java/math/Division.java b/luni/src/main/java/java/math/Division.java deleted file mode 100644 index d6427832c2..0000000000 --- a/luni/src/main/java/java/math/Division.java +++ /dev/null @@ -1,91 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package java.math; - -/** - * Static library that provides all operations related with division and modular - * arithmetic to {@link BigInteger}. Some methods are provided in both mutable - * and immutable way. There are several variants provided listed below: - * - * <ul type="circle"> - * <li> <b>Division</b> - * <ul type="circle"> - * <li>{@link BigInteger} division and remainder by {@link BigInteger}.</li> - * <li>{@link BigInteger} division and remainder by {@code int}.</li> - * <li><i>gcd</i> between {@link BigInteger} numbers.</li> - * </ul> - * </li> - * <li> <b>Modular arithmetic </b> - * <ul type="circle"> - * <li>Modular exponentiation between {@link BigInteger} numbers.</li> - * <li>Modular inverse of a {@link BigInteger} numbers.</li> - * </ul> - * </li> - *</ul> - */ -class Division { - - /** - * Divides an array by an integer value. Implements the Knuth's division - * algorithm. See D. Knuth, The Art of Computer Programming, vol. 2. - * - * @return remainder - */ - static int divideArrayByInt(int[] quotient, int[] dividend, final int dividendLength, - final int divisor) { - - long rem = 0; - long bLong = divisor & 0xffffffffL; - - for (int i = dividendLength - 1; i >= 0; i--) { - long temp = (rem << 32) | (dividend[i] & 0xffffffffL); - long quot; - if (temp >= 0) { - quot = (temp / bLong); - rem = (temp % bLong); - } else { - /* - * make the dividend positive shifting it right by 1 bit then - * get the quotient an remainder and correct them properly - */ - long aPos = temp >>> 1; - long bPos = divisor >>> 1; - quot = aPos / bPos; - rem = aPos % bPos; - // double the remainder and add 1 if a is odd - rem = (rem << 1) + (temp & 1); - if ((divisor & 1) != 0) { - // the divisor is odd - if (quot <= rem) { - rem -= quot; - } else { - if (quot - rem <= bLong) { - rem += bLong - quot; - quot -= 1; - } else { - rem += (bLong << 1) - quot; - quot -= 2; - } - } - } - } - quotient[i] = (int) (quot & 0xffffffffL); - } - return (int) rem; - } -} diff --git a/luni/src/main/java/java/math/Logical.java b/luni/src/main/java/java/math/Logical.java deleted file mode 100644 index 9de092437a..0000000000 --- a/luni/src/main/java/java/math/Logical.java +++ /dev/null @@ -1,773 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package java.math; - -/** - * The library implements some logical operations over {@code BigInteger}. The - * operations provided are listed below. - * <ul type="circle"> - * <li>not</li> - * <li>and</li> - * <li>andNot</li> - * <li>or</li> - * <li>xor</li> - * </ul> - */ -class Logical { - - /** Just to denote that this class can't be instantiated. */ - - private Logical() {} - - - /** @see BigInteger#not() */ - static BigInteger not(BigInteger val) { - if (val.sign == 0) { - return BigInteger.MINUS_ONE; - } - if (val.equals(BigInteger.MINUS_ONE)) { - return BigInteger.ZERO; - } - int[] resDigits = new int[val.numberLength + 1]; - int i; - - if (val.sign > 0) { - // ~val = -val + 1 - if (val.digits[val.numberLength - 1] != -1) { - for (i = 0; val.digits[i] == -1; i++) { - ; - } - } else { - for (i = 0; (i < val.numberLength) && (val.digits[i] == -1); i++) { - ; - } - if (i == val.numberLength) { - resDigits[i] = 1; - return new BigInteger(-val.sign, i + 1, resDigits); - } - } - // Here a carry 1 was generated - } else {// (val.sign < 0) - // ~val = -val - 1 - for (i = 0; val.digits[i] == 0; i++) { - resDigits[i] = -1; - } - // Here a borrow -1 was generated - } - // Now, the carry/borrow can be absorbed - resDigits[i] = val.digits[i] + val.sign; - // Copying the remaining unchanged digit - for (i++; i < val.numberLength; i++) { - resDigits[i] = val.digits[i]; - } - return new BigInteger(-val.sign, i, resDigits); - } - - /** @see BigInteger#and(BigInteger) */ - static BigInteger and(BigInteger val, BigInteger that) { - if (that.sign == 0 || val.sign == 0) { - return BigInteger.ZERO; - } - if (that.equals(BigInteger.MINUS_ONE)){ - return val; - } - if (val.equals(BigInteger.MINUS_ONE)) { - return that; - } - - if (val.sign > 0) { - if (that.sign > 0) { - return andPositive(val, that); - } else { - return andDiffSigns(val, that); - } - } else { - if (that.sign > 0) { - return andDiffSigns(that, val); - } else if (val.numberLength > that.numberLength) { - return andNegative(val, that); - } else { - return andNegative(that, val); - } - } - } - - /** @return sign = 1, magnitude = val.magnitude & that.magnitude*/ - static BigInteger andPositive(BigInteger val, BigInteger that) { - // PRE: both arguments are positive - int resLength = Math.min(val.numberLength, that.numberLength); - int i = Math.max(val.getFirstNonzeroDigit(), that.getFirstNonzeroDigit()); - - if (i >= resLength) { - return BigInteger.ZERO; - } - - int[] resDigits = new int[resLength]; - for ( ; i < resLength; i++) { - resDigits[i] = val.digits[i] & that.digits[i]; - } - - return new BigInteger(1, resLength, resDigits); - } - - /** @return sign = positive.magnitude & magnitude = -negative.magnitude */ - static BigInteger andDiffSigns(BigInteger positive, BigInteger negative) { - // PRE: positive is positive and negative is negative - int iPos = positive.getFirstNonzeroDigit(); - int iNeg = negative.getFirstNonzeroDigit(); - - // Look if the trailing zeros of the negative will "blank" all - // the positive digits - if (iNeg >= positive.numberLength) { - return BigInteger.ZERO; - } - int resLength = positive.numberLength; - int[] resDigits = new int[resLength]; - - // Must start from max(iPos, iNeg) - int i = Math.max(iPos, iNeg); - if (i == iNeg) { - resDigits[i] = -negative.digits[i] & positive.digits[i]; - i++; - } - int limit = Math.min(negative.numberLength, positive.numberLength); - for ( ; i < limit; i++) { - resDigits[i] = ~negative.digits[i] & positive.digits[i]; - } - // if the negative was shorter must copy the remaining digits - // from positive - if (i >= negative.numberLength) { - for ( ; i < positive.numberLength; i++) { - resDigits[i] = positive.digits[i]; - } - } // else positive ended and must "copy" virtual 0's, do nothing then - - return new BigInteger(1, resLength, resDigits); - } - - /** @return sign = -1, magnitude = -(-longer.magnitude & -shorter.magnitude)*/ - static BigInteger andNegative(BigInteger longer, BigInteger shorter) { - // PRE: longer and shorter are negative - // PRE: longer has at least as many digits as shorter - int iLonger = longer.getFirstNonzeroDigit(); - int iShorter = shorter.getFirstNonzeroDigit(); - - // Does shorter matter? - if (iLonger >= shorter.numberLength) { - return longer; - } - - int resLength; - int[] resDigits; - int i = Math.max(iShorter, iLonger); - int digit; - if (iShorter > iLonger) { - digit = -shorter.digits[i] & ~longer.digits[i]; - } else if (iShorter < iLonger) { - digit = ~shorter.digits[i] & -longer.digits[i]; - } else { - digit = -shorter.digits[i] & -longer.digits[i]; - } - if (digit == 0) { - for (i++; i < shorter.numberLength && (digit = ~(longer.digits[i] | shorter.digits[i])) == 0; i++) - ; // digit = ~longer.digits[i] & ~shorter.digits[i] - if (digit == 0) { - // shorter has only the remaining virtual sign bits - for ( ; i < longer.numberLength && (digit = ~longer.digits[i]) == 0; i++) - ; - if (digit == 0) { - resLength = longer.numberLength + 1; - resDigits = new int[resLength]; - resDigits[resLength - 1] = 1; - - return new BigInteger(-1, resLength, resDigits); - } - } - } - resLength = longer.numberLength; - resDigits = new int[resLength]; - resDigits[i] = -digit; - for (i++; i < shorter.numberLength; i++){ - // resDigits[i] = ~(~longer.digits[i] & ~shorter.digits[i];) - resDigits[i] = longer.digits[i] | shorter.digits[i]; - } - // shorter has only the remaining virtual sign bits - for ( ; i < longer.numberLength; i++){ - resDigits[i] = longer.digits[i]; - } - - return new BigInteger(-1, resLength, resDigits); - } - - /** @see BigInteger#andNot(BigInteger) */ - static BigInteger andNot(BigInteger val, BigInteger that) { - if (that.sign == 0 ) { - return val; - } - if (val.sign == 0) { - return BigInteger.ZERO; - } - if (val.equals(BigInteger.MINUS_ONE)) { - return that.not(); - } - if (that.equals(BigInteger.MINUS_ONE)){ - return BigInteger.ZERO; - } - - //if val == that, return 0 - - if (val.sign > 0) { - if (that.sign > 0) { - return andNotPositive(val, that); - } else { - return andNotPositiveNegative(val, that); - } - } else { - if (that.sign > 0) { - return andNotNegativePositive(val, that); - } else { - return andNotNegative(val, that); - } - } - } - - /** @return sign = 1, magnitude = val.magnitude & ~that.magnitude*/ - static BigInteger andNotPositive(BigInteger val, BigInteger that) { - // PRE: both arguments are positive - int[] resDigits = new int[val.numberLength]; - - int limit = Math.min(val.numberLength, that.numberLength); - int i; - for (i = val.getFirstNonzeroDigit(); i < limit; i++) { - resDigits[i] = val.digits[i] & ~that.digits[i]; - } - for ( ; i < val.numberLength; i++) { - resDigits[i] = val.digits[i]; - } - - return new BigInteger(1, val.numberLength, resDigits); - } - - /** @return sign = 1, magnitude = positive.magnitude & ~(-negative.magnitude)*/ - static BigInteger andNotPositiveNegative(BigInteger positive, BigInteger negative) { - // PRE: positive > 0 && negative < 0 - int iNeg = negative.getFirstNonzeroDigit(); - int iPos = positive.getFirstNonzeroDigit(); - - if (iNeg >= positive.numberLength) { - return positive; - } - - int resLength = Math.min(positive.numberLength, negative.numberLength); - int[] resDigits = new int[resLength]; - - // Always start from first non zero of positive - int i = iPos; - for ( ; i < iNeg; i++) { - // resDigits[i] = positive.digits[i] & -1 (~0) - resDigits[i] = positive.digits[i]; - } - if (i == iNeg) { - resDigits[i] = positive.digits[i] & (negative.digits[i] - 1); - i++; - } - for ( ; i < resLength; i++) { - // resDigits[i] = positive.digits[i] & ~(~negative.digits[i]); - resDigits[i] = positive.digits[i] & negative.digits[i]; - } - - return new BigInteger(1, resLength, resDigits); - } - - /** @return sign = -1, magnitude = -(-negative.magnitude & ~positive.magnitude)*/ - static BigInteger andNotNegativePositive(BigInteger negative, BigInteger positive) { - // PRE: negative < 0 && positive > 0 - int resLength; - int[] resDigits; - int limit; - int digit; - - int iNeg = negative.getFirstNonzeroDigit(); - int iPos = positive.getFirstNonzeroDigit(); - - if (iNeg >= positive.numberLength) { - return negative; - } - - resLength = Math.max(negative.numberLength, positive.numberLength); - int i = iNeg; - if (iPos > iNeg) { - resDigits = new int[resLength]; - limit = Math.min(negative.numberLength, iPos); - for ( ; i < limit; i++) { - // 1st case: resDigits [i] = -(-negative.digits[i] & (~0)) - // otherwise: resDigits[i] = ~(~negative.digits[i] & ~0) ; - resDigits[i] = negative.digits[i]; - } - if (i == negative.numberLength) { - for (i = iPos; i < positive.numberLength; i++) { - // resDigits[i] = ~(~positive.digits[i] & -1); - resDigits[i] = positive.digits[i]; - } - } - } else { - digit = -negative.digits[i] & ~positive.digits[i]; - if (digit == 0) { - limit = Math.min(positive.numberLength, negative.numberLength); - for (i++; i < limit && (digit = ~(negative.digits[i] | positive.digits[i])) == 0; i++) - ; // digit = ~negative.digits[i] & ~positive.digits[i] - if (digit == 0) { - // the shorter has only the remaining virtual sign bits - for ( ; i < positive.numberLength && (digit = ~positive.digits[i]) == 0; i++) - ; // digit = -1 & ~positive.digits[i] - for ( ; i < negative.numberLength && (digit = ~negative.digits[i]) == 0; i++) - ; // digit = ~negative.digits[i] & ~0 - if (digit == 0) { - resLength++; - resDigits = new int[resLength]; - resDigits[resLength - 1] = 1; - - return new BigInteger(-1, resLength, resDigits); - } - } - } - resDigits = new int[resLength]; - resDigits[i] = -digit; - i++; - } - - limit = Math.min(positive.numberLength, negative.numberLength); - for ( ; i < limit; i++) { - //resDigits[i] = ~(~negative.digits[i] & ~positive.digits[i]); - resDigits[i] = negative.digits[i] | positive.digits[i]; - } - // Actually one of the next two cycles will be executed - for ( ; i < negative.numberLength; i++) { - resDigits[i] = negative.digits[i]; - } - for ( ; i < positive.numberLength; i++) { - resDigits[i] = positive.digits[i]; - } - - return new BigInteger(-1, resLength, resDigits); - } - - /** @return sign = 1, magnitude = -val.magnitude & ~(-that.magnitude)*/ - static BigInteger andNotNegative(BigInteger val, BigInteger that) { - // PRE: val < 0 && that < 0 - int iVal = val.getFirstNonzeroDigit(); - int iThat = that.getFirstNonzeroDigit(); - - if (iVal >= that.numberLength) { - return BigInteger.ZERO; - } - - int resLength = that.numberLength; - int[] resDigits = new int[resLength]; - int limit; - int i = iVal; - if (iVal < iThat) { - // resDigits[i] = -val.digits[i] & -1; - resDigits[i] = -val.digits[i]; - limit = Math.min(val.numberLength, iThat); - for (i++; i < limit; i++) { - // resDigits[i] = ~val.digits[i] & -1; - resDigits[i] = ~val.digits[i]; - } - if (i == val.numberLength) { - for ( ; i < iThat; i++) { - // resDigits[i] = -1 & -1; - resDigits[i] = -1; - } - // resDigits[i] = -1 & ~-that.digits[i]; - resDigits[i] = that.digits[i] - 1; - } else { - // resDigits[i] = ~val.digits[i] & ~-that.digits[i]; - resDigits[i] = ~val.digits[i] & (that.digits[i] - 1); - } - } else if (iThat < iVal ) { - // resDigits[i] = -val.digits[i] & ~~that.digits[i]; - resDigits[i] = -val.digits[i] & that.digits[i]; - } else { - // resDigits[i] = -val.digits[i] & ~-that.digits[i]; - resDigits[i] = -val.digits[i] & (that.digits[i] - 1); - } - - limit = Math.min(val.numberLength, that.numberLength); - for (i++; i < limit; i++) { - // resDigits[i] = ~val.digits[i] & ~~that.digits[i]; - resDigits[i] = ~val.digits[i] & that.digits[i]; - } - for ( ; i < that.numberLength; i++) { - // resDigits[i] = -1 & ~~that.digits[i]; - resDigits[i] = that.digits[i]; - } - - return new BigInteger(1, resLength, resDigits); - } - - /** @see BigInteger#or(BigInteger) */ - static BigInteger or(BigInteger val, BigInteger that) { - if (that.equals(BigInteger.MINUS_ONE) || val.equals(BigInteger.MINUS_ONE)) { - return BigInteger.MINUS_ONE; - } - if (that.sign == 0) { - return val; - } - if (val.sign == 0) { - return that; - } - - if (val.sign > 0) { - if (that.sign > 0) { - if (val.numberLength > that.numberLength) { - return orPositive(val, that); - } else { - return orPositive(that, val); - } - } else { - return orDiffSigns(val, that); - } - } else { - if (that.sign > 0) { - return orDiffSigns(that, val); - } else if (that.getFirstNonzeroDigit() > val.getFirstNonzeroDigit()) { - return orNegative(that, val); - } else { - return orNegative(val, that); - } - } - } - - /** @return sign = 1, magnitude = longer.magnitude | shorter.magnitude*/ - static BigInteger orPositive(BigInteger longer, BigInteger shorter) { - // PRE: longer and shorter are positive; - // PRE: longer has at least as many digits as shorter - int resLength = longer.numberLength; - int[] resDigits = new int[resLength]; - - int i; - for (i = 0; i < shorter.numberLength; i++) { - resDigits[i] = longer.digits[i] | shorter.digits[i]; - } - for ( ; i < resLength; i++) { - resDigits[i] = longer.digits[i]; - } - - return new BigInteger(1, resLength, resDigits); - } - - /** @return sign = -1, magnitude = -(-val.magnitude | -that.magnitude) */ - static BigInteger orNegative(BigInteger val, BigInteger that){ - // PRE: val and that are negative; - // PRE: val has at least as many trailing zeros digits as that - int iThat = that.getFirstNonzeroDigit(); - int iVal = val.getFirstNonzeroDigit(); - int i; - - if (iVal >= that.numberLength) { - return that; - }else if (iThat >= val.numberLength) { - return val; - } - - int resLength = Math.min(val.numberLength, that.numberLength); - int[] resDigits = new int[resLength]; - - //Looking for the first non-zero digit of the result - if (iThat == iVal) { - resDigits[iVal] = -(-val.digits[iVal] | -that.digits[iVal]); - i = iVal; - } else { - for (i = iThat; i < iVal; i++) { - resDigits[i] = that.digits[i]; - } - resDigits[i] = that.digits[i] & (val.digits[i] - 1); - } - - for (i++; i < resLength; i++) { - resDigits[i] = val.digits[i] & that.digits[i]; - } - - return new BigInteger(-1, resLength, resDigits); - } - - /** @return sign = -1, magnitude = -(positive.magnitude | -negative.magnitude) */ - static BigInteger orDiffSigns(BigInteger positive, BigInteger negative){ - // Jumping over the least significant zero bits - int iNeg = negative.getFirstNonzeroDigit(); - int iPos = positive.getFirstNonzeroDigit(); - int i; - int limit; - - // Look if the trailing zeros of the positive will "copy" all - // the negative digits - if (iPos >= negative.numberLength) { - return negative; - } - int resLength = negative.numberLength; - int[] resDigits = new int[resLength]; - - if (iNeg < iPos ) { - // We know for sure that this will - // be the first non zero digit in the result - for (i = iNeg; i < iPos; i++) { - resDigits[i] = negative.digits[i]; - } - } else if (iPos < iNeg) { - i = iPos; - resDigits[i] = -positive.digits[i]; - limit = Math.min(positive.numberLength, iNeg); - for (i++; i < limit; i++ ) { - resDigits[i] = ~positive.digits[i]; - } - if (i != positive.numberLength) { - resDigits[i] = ~(-negative.digits[i] | positive.digits[i]); - } else{ - for (; i<iNeg; i++) { - resDigits[i] = -1; - } - // resDigits[i] = ~(-negative.digits[i] | 0); - resDigits[i] = negative.digits[i] - 1; - } - i++; - } else {// iNeg == iPos - // Applying two complement to negative and to result - i = iPos; - resDigits[i] = -(-negative.digits[i] | positive.digits[i]); - i++; - } - limit = Math.min(negative.numberLength, positive.numberLength); - for (; i < limit; i++) { - // Applying two complement to negative and to result - // resDigits[i] = ~(~negative.digits[i] | positive.digits[i] ); - resDigits[i] = negative.digits[i] & ~positive.digits[i]; - } - for ( ; i < negative.numberLength; i++) { - resDigits[i] = negative.digits[i]; - } - - return new BigInteger(-1, resLength, resDigits); - } - - /** @see BigInteger#xor(BigInteger) */ - static BigInteger xor(BigInteger val, BigInteger that) { - if (that.sign == 0) { - return val; - } - if (val.sign == 0) { - return that; - } - if (that.equals(BigInteger.MINUS_ONE)) { - return val.not(); - } - if (val.equals(BigInteger.MINUS_ONE)) { - return that.not(); - } - - if (val.sign > 0) { - if (that.sign > 0) { - if (val.numberLength > that.numberLength) { - return xorPositive(val, that); - } else { - return xorPositive(that, val); - } - } else { - return xorDiffSigns(val, that); - } - } else { - if (that.sign > 0) { - return xorDiffSigns(that, val); - } else if (that.getFirstNonzeroDigit() > val.getFirstNonzeroDigit()) { - return xorNegative(that, val); - } else { - return xorNegative(val, that); - } - } - } - - /** @return sign = 0, magnitude = longer.magnitude | shorter.magnitude */ - static BigInteger xorPositive(BigInteger longer, BigInteger shorter) { - // PRE: longer and shorter are positive; - // PRE: longer has at least as many digits as shorter - int resLength = longer.numberLength; - int[] resDigits = new int[resLength]; - int i = Math.min(longer.getFirstNonzeroDigit(), shorter.getFirstNonzeroDigit()); - for ( ; i < shorter.numberLength; i++) { - resDigits[i] = longer.digits[i] ^ shorter.digits[i]; - } - for ( ; i < longer.numberLength; i++ ){ - resDigits[i] = longer.digits[i]; - } - - return new BigInteger(1, resLength, resDigits); - } - - /** @return sign = 0, magnitude = -val.magnitude ^ -that.magnitude */ - static BigInteger xorNegative(BigInteger val, BigInteger that){ - // PRE: val and that are negative - // PRE: val has at least as many trailing zero digits as that - int resLength = Math.max(val.numberLength, that.numberLength); - int[] resDigits = new int[resLength]; - int iVal = val.getFirstNonzeroDigit(); - int iThat = that.getFirstNonzeroDigit(); - int i = iThat; - int limit; - - - if (iVal == iThat) { - resDigits[i] = -val.digits[i] ^ -that.digits[i]; - } else { - resDigits[i] = -that.digits[i]; - limit = Math.min(that.numberLength, iVal); - for (i++; i < limit; i++) { - resDigits[i] = ~that.digits[i]; - } - // Remains digits in that? - if (i == that.numberLength) { - //Jumping over the remaining zero to the first non one - for ( ;i < iVal; i++) { - //resDigits[i] = 0 ^ -1; - resDigits[i] = -1; - } - //resDigits[i] = -val.digits[i] ^ -1; - resDigits[i] = val.digits[i] - 1; - } else { - resDigits[i] = -val.digits[i] ^ ~that.digits[i]; - } - } - - limit = Math.min(val.numberLength, that.numberLength); - //Perform ^ between that al val until that ends - for (i++; i < limit; i++) { - //resDigits[i] = ~val.digits[i] ^ ~that.digits[i]; - resDigits[i] = val.digits[i] ^ that.digits[i]; - } - //Perform ^ between val digits and -1 until val ends - for ( ; i < val.numberLength; i++) { - //resDigits[i] = ~val.digits[i] ^ -1 ; - resDigits[i] = val.digits[i] ; - } - for ( ; i < that.numberLength; i++) { - //resDigits[i] = -1 ^ ~that.digits[i] ; - resDigits[i] = that.digits[i]; - } - - return new BigInteger(1, resLength, resDigits); - } - - /** @return sign = 1, magnitude = -(positive.magnitude ^ -negative.magnitude)*/ - static BigInteger xorDiffSigns(BigInteger positive, BigInteger negative){ - int resLength = Math.max(negative.numberLength, positive.numberLength); - int[] resDigits; - int iNeg = negative.getFirstNonzeroDigit(); - int iPos = positive.getFirstNonzeroDigit(); - int i; - int limit; - - //The first - if (iNeg < iPos) { - resDigits = new int[resLength]; - i = iNeg; - //resDigits[i] = -(-negative.digits[i]); - resDigits[i] = negative.digits[i]; - limit = Math.min(negative.numberLength, iPos); - //Skip the positive digits while they are zeros - for (i++; i < limit; i++) { - //resDigits[i] = ~(~negative.digits[i]); - resDigits[i] = negative.digits[i]; - } - //if the negative has no more elements, must fill the - //result with the remaining digits of the positive - if (i == negative.numberLength) { - for ( ; i < positive.numberLength; i++) { - //resDigits[i] = ~(positive.digits[i] ^ -1) -> ~(~positive.digits[i]) - resDigits[i] = positive.digits[i]; - } - } - } else if (iPos < iNeg) { - resDigits = new int[resLength]; - i = iPos; - //Applying two complement to the first non-zero digit of the result - resDigits[i] = -positive.digits[i]; - limit = Math.min(positive.numberLength, iNeg); - for (i++; i < limit; i++) { - //Continue applying two complement the result - resDigits[i] = ~positive.digits[i]; - } - //When the first non-zero digit of the negative is reached, must apply - //two complement (arithmetic negation) to it, and then operate - if (i == iNeg) { - resDigits[i] = ~(positive.digits[i] ^ -negative.digits[i]); - i++; - } else { - //if the positive has no more elements must fill the remaining digits with - //the negative ones - for ( ; i < iNeg; i++) { - // resDigits[i] = ~(0 ^ 0) - resDigits[i] = -1; - } - for ( ; i < negative.numberLength; i++) { - //resDigits[i] = ~(~negative.digits[i] ^ 0) - resDigits[i] = negative.digits[i]; - } - } - } else { - //The first non-zero digit of the positive and negative are the same - i = iNeg; - int digit = positive.digits[i] ^ -negative.digits[i]; - if (digit == 0) { - limit = Math.min(positive.numberLength, negative.numberLength); - for (i++; i < limit && (digit = positive.digits[i] ^ ~negative.digits[i]) == 0; i++) - ; - if (digit == 0) { - // shorter has only the remaining virtual sign bits - for ( ; i < positive.numberLength && (digit = ~positive.digits[i]) == 0; i++) - ; - for ( ; i < negative.numberLength && (digit = ~negative.digits[i]) == 0; i++) - ; - if (digit == 0) { - resLength = resLength + 1; - resDigits = new int[resLength]; - resDigits[resLength - 1] = 1; - - return new BigInteger(-1, resLength, resDigits); - } - } - } - resDigits = new int[resLength]; - resDigits[i] = -digit; - i++; - } - - limit = Math.min(negative.numberLength, positive.numberLength); - for ( ; i < limit; i++) { - resDigits[i] = ~(~negative.digits[i] ^ positive.digits[i]); - } - for ( ; i < positive.numberLength; i++) { - // resDigits[i] = ~(positive.digits[i] ^ -1) - resDigits[i] = positive.digits[i]; - } - for ( ; i < negative.numberLength; i++) { - // resDigits[i] = ~(0 ^ ~negative.digits[i]) - resDigits[i] = negative.digits[i]; - } - - return new BigInteger(-1, resLength, resDigits); - } -} diff --git a/luni/src/main/java/java/math/MathContext.java b/luni/src/main/java/java/math/MathContext.java deleted file mode 100644 index 6f3f1edf6a..0000000000 --- a/luni/src/main/java/java/math/MathContext.java +++ /dev/null @@ -1,249 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package java.math; - -import java.io.IOException; -import java.io.ObjectInputStream; -import java.io.Serializable; -import java.io.StreamCorruptedException; - -/** - * Immutable objects describing settings such as rounding mode and digit - * precision for the numerical operations provided by class {@link BigDecimal}. - */ -public final class MathContext implements Serializable { - private static final long serialVersionUID = 5579720004786848255L; - - /** - * A {@code MathContext} which corresponds to the <a href="http://en.wikipedia.org/wiki/IEEE_754-1985">IEEE 754</a> quadruple - * decimal precision format: 34 digit precision and - * {@link RoundingMode#HALF_EVEN} rounding. - */ - public static final MathContext DECIMAL128 = new MathContext(34, RoundingMode.HALF_EVEN); - - /** - * A {@code MathContext} which corresponds to the <a href="http://en.wikipedia.org/wiki/IEEE_754-1985">IEEE 754</a> single decimal - * precision format: 7 digit precision and {@link RoundingMode#HALF_EVEN} - * rounding. - */ - public static final MathContext DECIMAL32 = new MathContext(7, RoundingMode.HALF_EVEN); - - /** - * A {@code MathContext} which corresponds to the <a href="http://en.wikipedia.org/wiki/IEEE_754-1985">IEEE 754</a> double decimal - * precision format: 16 digit precision and {@link RoundingMode#HALF_EVEN} - * rounding. - */ - public static final MathContext DECIMAL64 = new MathContext(16, RoundingMode.HALF_EVEN); - - /** - * A {@code MathContext} for unlimited precision with - * {@link RoundingMode#HALF_UP} rounding. - */ - public static final MathContext UNLIMITED = new MathContext(0, RoundingMode.HALF_UP); - - /** - * The number of digits to be used for an operation; results are rounded to - * this precision. - */ - private final int precision; - - /** - * A {@code RoundingMode} object which specifies the algorithm to be used - * for rounding. - */ - private final RoundingMode roundingMode; - - /** - * Constructs a new {@code MathContext} with the specified precision and - * with the rounding mode {@link RoundingMode#HALF_UP HALF_UP}. If the - * precision passed is zero, then this implies that the computations have to - * be performed exact, the rounding mode in this case is irrelevant. - * - * @param precision - * the precision for the new {@code MathContext}. - * @throws IllegalArgumentException - * if {@code precision < 0}. - */ - public MathContext(int precision) { - this(precision, RoundingMode.HALF_UP); - } - - /** - * Constructs a new {@code MathContext} with the specified precision and - * with the specified rounding mode. If the precision passed is zero, then - * this implies that the computations have to be performed exact, the - * rounding mode in this case is irrelevant. - * - * @param precision - * the precision for the new {@code MathContext}. - * @param roundingMode - * the rounding mode for the new {@code MathContext}. - * @throws IllegalArgumentException - * if {@code precision < 0}. - * @throws NullPointerException - * if {@code roundingMode} is {@code null}. - */ - public MathContext(int precision, RoundingMode roundingMode) { - this.precision = precision; - this.roundingMode = roundingMode; - checkValid(); - } - - /** - * Constructs a new {@code MathContext} from a string. The string has to - * specify the precision and the rounding mode to be used and has to follow - * the following syntax: "precision=<precision> roundingMode=<roundingMode>" - * This is the same form as the one returned by the {@link #toString} - * method. - * - * @throws IllegalArgumentException - * if the string is not in the correct format or if the - * precision specified is < 0. - */ - public MathContext(String s) { - int precisionLength = "precision=".length(); - int roundingModeLength = "roundingMode=".length(); - - int spaceIndex; - if (!s.startsWith("precision=") || (spaceIndex = s.indexOf(' ', precisionLength)) == -1) { - throw invalidMathContext("Missing precision", s); - } - String precisionString = s.substring(precisionLength, spaceIndex); - try { - this.precision = Integer.parseInt(precisionString); - } catch (NumberFormatException nfe) { - throw invalidMathContext("Bad precision", s); - } - - int roundingModeStart = spaceIndex + 1; - if (!s.regionMatches(roundingModeStart, "roundingMode=", 0, roundingModeLength)) { - throw invalidMathContext("Missing rounding mode", s); - } - roundingModeStart += roundingModeLength; - this.roundingMode = RoundingMode.valueOf(s.substring(roundingModeStart)); - - checkValid(); - } - - private IllegalArgumentException invalidMathContext(String reason, String s) { - throw new IllegalArgumentException(reason + ": " + s); - } - - private void checkValid() { - if (precision < 0) { - throw new IllegalArgumentException("Negative precision: " + precision); - } - if (roundingMode == null) { - throw new NullPointerException("roundingMode == null"); - } - } - - /** - * Returns the precision. The precision is the number of digits used for an - * operation. Results are rounded to this precision. The precision is - * guaranteed to be non negative. If the precision is zero, then the - * computations have to be performed exact, results are not rounded in this - * case. - * - * @return the precision. - */ - public int getPrecision() { - return precision; - } - - /** - * Returns the rounding mode. The rounding mode is the strategy to be used - * to round results. - * <p> - * The rounding mode is one of - * {@link RoundingMode#UP}, - * {@link RoundingMode#DOWN}, - * {@link RoundingMode#CEILING}, - * {@link RoundingMode#FLOOR}, - * {@link RoundingMode#HALF_UP}, - * {@link RoundingMode#HALF_DOWN}, - * {@link RoundingMode#HALF_EVEN}, or - * {@link RoundingMode#UNNECESSARY}. - * - * @return the rounding mode. - */ - public RoundingMode getRoundingMode() { - return roundingMode; - } - - /** - * Returns true if x is a {@code MathContext} with the same precision - * setting and the same rounding mode as this {@code MathContext} instance. - * - * @param x - * object to be compared. - * @return {@code true} if this {@code MathContext} instance is equal to the - * {@code x} argument; {@code false} otherwise. - */ - @Override - public boolean equals(Object x) { - return ((x instanceof MathContext) - && (((MathContext) x).getPrecision() == precision) && (((MathContext) x) - .getRoundingMode() == roundingMode)); - } - - /** - * Returns the hash code for this {@code MathContext} instance. - * - * @return the hash code for this {@code MathContext}. - */ - @Override - public int hashCode() { - // Make place for the necessary bits to represent 8 rounding modes - return ((precision << 3) | roundingMode.ordinal()); - } - - /** - * Returns the string representation for this {@code MathContext} instance. - * The string has the form - * {@code - * "precision=<precision> roundingMode=<roundingMode>" - * } where {@code <precision>} is an integer describing the number - * of digits used for operations and {@code <roundingMode>} is the - * string representation of the rounding mode. - * - * @return a string representation for this {@code MathContext} instance - */ - @Override - public String toString() { - return "precision=" + precision + " roundingMode=" + roundingMode; - } - - /** - * Makes checks upon deserialization of a {@code MathContext} instance. - * Checks whether {@code precision >= 0} and {@code roundingMode != null} - * - * @throws StreamCorruptedException - * if {@code precision < 0} - * @throws StreamCorruptedException - * if {@code roundingMode == null} - */ - private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException { - s.defaultReadObject(); - try { - checkValid(); - } catch (Exception ex) { - throw new StreamCorruptedException(ex.getMessage()); - } - } -} diff --git a/luni/src/main/java/java/math/Multiplication.java b/luni/src/main/java/java/math/Multiplication.java deleted file mode 100644 index 2a4285b56e..0000000000 --- a/luni/src/main/java/java/math/Multiplication.java +++ /dev/null @@ -1,187 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package java.math; - -/** - * Static library that provides all multiplication of {@link BigInteger} methods. - */ -class Multiplication { - - /** Just to denote that this class can't be instantiated. */ - private Multiplication() {} - - // BEGIN Android-removed - // /** - // * Break point in digits (number of {@code int} elements) - // * between Karatsuba and Pencil and Paper multiply. - // */ - // static final int whenUseKaratsuba = 63; // an heuristic value - // END Android-removed - - /** - * An array with powers of ten that fit in the type {@code int}. - * ({@code 10^0,10^1,...,10^9}) - */ - static final int[] tenPows = { - 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 - }; - - /** - * An array with powers of five that fit in the type {@code int}. - * ({@code 5^0,5^1,...,5^13}) - */ - static final int[] fivePows = { - 1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, - 1953125, 9765625, 48828125, 244140625, 1220703125 - }; - - /** - * An array with the first powers of ten in {@code BigInteger} version. - * ({@code 10^0,10^1,...,10^31}) - */ - static final BigInteger[] bigTenPows = new BigInteger[32]; - - /** - * An array with the first powers of five in {@code BigInteger} version. - * ({@code 5^0,5^1,...,5^31}) - */ - static final BigInteger bigFivePows[] = new BigInteger[32]; - - - - static { - int i; - long fivePow = 1L; - - for (i = 0; i <= 18; i++) { - bigFivePows[i] = BigInteger.valueOf(fivePow); - bigTenPows[i] = BigInteger.valueOf(fivePow << i); - fivePow *= 5; - } - for (; i < bigTenPows.length; i++) { - bigFivePows[i] = bigFivePows[i - 1].multiply(bigFivePows[1]); - bigTenPows[i] = bigTenPows[i - 1].multiply(BigInteger.TEN); - } - } - - // BEGIN android-note: multiply has been removed in favor of using OpenSSL BIGNUM - // END android-note - - /** - * Multiplies a number by a positive integer. - * @param val an arbitrary {@code BigInteger} - * @param factor a positive {@code int} number - * @return {@code val * factor} - */ - static BigInteger multiplyByPositiveInt(BigInteger val, int factor) { - BigInt bi = val.getBigInt().copy(); - bi.multiplyByPositiveInt(factor); - return new BigInteger(bi); - } - - /** - * Multiplies a number by a power of ten. - * This method is used in {@code BigDecimal} class. - * @param val the number to be multiplied - * @param exp a positive {@code long} exponent - * @return {@code val * 10<sup>exp</sup>} - */ - static BigInteger multiplyByTenPow(BigInteger val, long exp) { - // PRE: exp >= 0 - return ((exp < tenPows.length) - ? multiplyByPositiveInt(val, tenPows[(int)exp]) - : val.multiply(powerOf10(exp))); - } - - /** - * It calculates a power of ten, which exponent could be out of 32-bit range. - * Note that internally this method will be used in the worst case with - * an exponent equals to: {@code Integer.MAX_VALUE - Integer.MIN_VALUE}. - * @param exp the exponent of power of ten, it must be positive. - * @return a {@code BigInteger} with value {@code 10<sup>exp</sup>}. - */ - static BigInteger powerOf10(long exp) { - // PRE: exp >= 0 - int intExp = (int)exp; - // "SMALL POWERS" - if (exp < bigTenPows.length) { - // The largest power that fit in 'long' type - return bigTenPows[intExp]; - } else if (exp <= 50) { - // To calculate: 10^exp - return BigInteger.TEN.pow(intExp); - } - - BigInteger res = null; - try { - // "LARGE POWERS" - if (exp <= Integer.MAX_VALUE) { - // To calculate: 5^exp * 2^exp - res = bigFivePows[1].pow(intExp).shiftLeft(intExp); - } else { - /* - * "HUGE POWERS" - * - * This branch probably won't be executed since the power of ten is too - * big. - */ - // To calculate: 5^exp - BigInteger powerOfFive = bigFivePows[1].pow(Integer.MAX_VALUE); - res = powerOfFive; - long longExp = exp - Integer.MAX_VALUE; - - intExp = (int) (exp % Integer.MAX_VALUE); - while (longExp > Integer.MAX_VALUE) { - res = res.multiply(powerOfFive); - longExp -= Integer.MAX_VALUE; - } - res = res.multiply(bigFivePows[1].pow(intExp)); - // To calculate: 5^exp << exp - res = res.shiftLeft(Integer.MAX_VALUE); - longExp = exp - Integer.MAX_VALUE; - while (longExp > Integer.MAX_VALUE) { - res = res.shiftLeft(Integer.MAX_VALUE); - longExp -= Integer.MAX_VALUE; - } - res = res.shiftLeft(intExp); - } - } catch (OutOfMemoryError error) { - throw new ArithmeticException(error.getMessage()); - } - - return res; - } - - /** - * Multiplies a number by a power of five. - * This method is used in {@code BigDecimal} class. - * @param val the number to be multiplied - * @param exp a positive {@code int} exponent - * @return {@code val * 5<sup>exp</sup>} - */ - static BigInteger multiplyByFivePow(BigInteger val, int exp) { - // PRE: exp >= 0 - if (exp < fivePows.length) { - return multiplyByPositiveInt(val, fivePows[exp]); - } else if (exp < bigFivePows.length) { - return val.multiply(bigFivePows[exp]); - } else {// Large powers of five - return val.multiply(bigFivePows[1].pow(exp)); - } - } -} diff --git a/luni/src/main/java/java/math/NativeBN.java b/luni/src/main/java/java/math/NativeBN.java deleted file mode 100644 index ab9b2e029f..0000000000 --- a/luni/src/main/java/java/math/NativeBN.java +++ /dev/null @@ -1,136 +0,0 @@ -/* - * Copyright (C) 2008 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package java.math; - -final class NativeBN { - - public static native long BN_new(); - // BIGNUM *BN_new(void); - - public static native void BN_free(long a); - // void BN_free(BIGNUM *a); - - public static native int BN_cmp(long a, long b); - // int BN_cmp(const BIGNUM *a, const BIGNUM *b); - - public static native void BN_copy(long to, long from); - // BIGNUM *BN_copy(BIGNUM *to, const BIGNUM *from); - - public static native void putLongInt(long a, long dw); - public static native void putULongInt(long a, long dw, boolean neg); - - public static native int BN_dec2bn(long a, String str); - // int BN_dec2bn(BIGNUM **a, const char *str); - - public static native int BN_hex2bn(long a, String str); - // int BN_hex2bn(BIGNUM **a, const char *str); - - public static native void BN_bin2bn(byte[] s, int len, boolean neg, long ret); - // BIGNUM * BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret); - // BN-Docu: s is taken as unsigned big endian; - // Additional parameter: neg. - - public static native void litEndInts2bn(int[] ints, int len, boolean neg, long ret); - - public static native void twosComp2bn(byte[] s, int len, long ret); - - - public static native long longInt(long a); - // unsigned long BN_get_word(BIGNUM *a); - - public static native String BN_bn2dec(long a); - // char * BN_bn2dec(const BIGNUM *a); - - public static native String BN_bn2hex(long a); - // char * BN_bn2hex(const BIGNUM *a); - - public static native byte[] BN_bn2bin(long a); - // Returns result byte[] AND NOT length. - // int BN_bn2bin(const BIGNUM *a, unsigned char *to); - - public static native int[] bn2litEndInts(long a); - - public static native int sign(long a); - // Returns -1, 0, 1 AND NOT boolean. - // #define BN_is_negative(a) ((a)->neg != 0) - - public static native void BN_set_negative(long b, int n); - // void BN_set_negative(BIGNUM *b, int n); - - public static native int bitLength(long a); - - public static native boolean BN_is_bit_set(long a, int n); - // int BN_is_bit_set(const BIGNUM *a, int n); - - public static native void BN_shift(long r, long a, int n); - // int BN_shift(BIGNUM *r, const BIGNUM *a, int n); - - public static native void BN_add_word(long a, int w); - // ATTENTION: w is treated as unsigned. - // int BN_add_word(BIGNUM *a, BN_ULONG w); - - public static native void BN_mul_word(long a, int w); - // ATTENTION: w is treated as unsigned. - // int BN_mul_word(BIGNUM *a, BN_ULONG w); - - public static native int BN_mod_word(long a, int w); - // ATTENTION: w is treated as unsigned. - // BN_ULONG BN_mod_word(BIGNUM *a, BN_ULONG w); - - public static native void BN_add(long r, long a, long b); - // int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); - - public static native void BN_sub(long r, long a, long b); - // int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); - - public static native void BN_gcd(long r, long a, long b); - // int BN_gcd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); - - public static native void BN_mul(long r, long a, long b); - // int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); - - public static native void BN_exp(long r, long a, long p); - // int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx); - - public static native void BN_div(long dv, long rem, long m, long d); - // int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx); - - public static native void BN_nnmod(long r, long a, long m); - // int BN_nnmod(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); - - public static native void BN_mod_exp(long r, long a, long p, long m); - // int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx); - - public static native void BN_mod_inverse(long ret, long a, long n); - // BIGNUM * BN_mod_inverse(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx); - - - public static native void BN_generate_prime_ex(long ret, int bits, boolean safe, - long add, long rem); - // int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, - // const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb); - - public static native boolean BN_primality_test(long candidate, int checks, - boolean do_trial_division); - // int BN_primality_test(int *is_probably_prime, const BIGNUM *candidate, int checks, - // BN_CTX *ctx, int do_trial_division, BN_GENCB *cb); - // Returns *is_probably_prime on success and throws an exception on error. - - public static native long getNativeFinalizer(); - // &BN_free - -} diff --git a/luni/src/main/java/java/math/Primality.java b/luni/src/main/java/java/math/Primality.java deleted file mode 100644 index eacc8935bf..0000000000 --- a/luni/src/main/java/java/math/Primality.java +++ /dev/null @@ -1,145 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package java.math; - -import java.util.Arrays; - -/** - * Provides primality probabilistic methods. - */ -class Primality { - - /** Just to denote that this class can't be instantiated. */ - private Primality() {} - - /** All prime numbers with bit length lesser than 10 bits. */ - private static final int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, - 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, - 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, - 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, - 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, - 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, - 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, - 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, - 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, - 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, - 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, - 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, - 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, - 1013, 1019, 1021 }; - - /** All {@code BigInteger} prime numbers with bit length lesser than 10 bits. */ - private static final BigInteger BIprimes[] = new BigInteger[primes.length]; - -// /** -// * It encodes how many iterations of Miller-Rabin test are need to get an -// * error bound not greater than {@code 2<sup>(-100)</sup>}. For example: -// * for a {@code 1000}-bit number we need {@code 4} iterations, since -// * {@code BITS[3] < 1000 <= BITS[4]}. -// */ -// private static final int[] BITS = { 0, 0, 1854, 1233, 927, 747, 627, 543, -// 480, 431, 393, 361, 335, 314, 295, 279, 265, 253, 242, 232, 223, -// 216, 181, 169, 158, 150, 145, 140, 136, 132, 127, 123, 119, 114, -// 110, 105, 101, 96, 92, 87, 83, 78, 73, 69, 64, 59, 54, 49, 44, 38, -// 32, 26, 1 }; -// -// /** -// * It encodes how many i-bit primes there are in the table for -// * {@code i=2,...,10}. For example {@code offsetPrimes[6]} says that from -// * index {@code 11} exists {@code 7} consecutive {@code 6}-bit prime -// * numbers in the array. -// */ -// private static final int[][] offsetPrimes = { null, null, { 0, 2 }, -// { 2, 2 }, { 4, 2 }, { 6, 5 }, { 11, 7 }, { 18, 13 }, { 31, 23 }, -// { 54, 43 }, { 97, 75 } }; - - static {// To initialize the dual table of BigInteger primes - for (int i = 0; i < primes.length; i++) { - BIprimes[i] = BigInteger.valueOf(primes[i]); - } - } - - /** - * It uses the sieve of Eratosthenes to discard several composite numbers in - * some appropriate range (at the moment {@code [this, this + 1024]}). After - * this process it applies the Miller-Rabin test to the numbers that were - * not discarded in the sieve. - * - * @see BigInteger#nextProbablePrime() - */ - static BigInteger nextProbablePrime(BigInteger n) { - // PRE: n >= 0 - int i, j; -// int certainty; - int gapSize = 1024; // for searching of the next probable prime number - int[] modules = new int[primes.length]; - boolean isDivisible[] = new boolean[gapSize]; - BigInt ni = n.getBigInt(); - // If n < "last prime of table" searches next prime in the table - if (ni.bitLength() <= 10) { - int l = (int)ni.longInt(); - if (l < primes[primes.length - 1]) { - for (i = 0; l >= primes[i]; i++) {} - return BIprimes[i]; - } - } - - BigInt startPoint = ni.copy(); - BigInt probPrime = new BigInt(); - - // Fix startPoint to "next odd number": - startPoint.addPositiveInt(BigInt.remainderByPositiveInt(ni, 2) + 1); - -// // To set the improved certainty of Miller-Rabin -// j = startPoint.bitLength(); -// for (certainty = 2; j < BITS[certainty]; certainty++) { -// ; -// } - - // To calculate modules: N mod p1, N mod p2, ... for first primes. - for (i = 0; i < primes.length; i++) { - modules[i] = BigInt.remainderByPositiveInt(startPoint, primes[i]) - gapSize; - } - while (true) { - // At this point, all numbers in the gap are initialized as - // probably primes - Arrays.fill(isDivisible, false); - // To discard multiples of first primes - for (i = 0; i < primes.length; i++) { - modules[i] = (modules[i] + gapSize) % primes[i]; - j = (modules[i] == 0) ? 0 : (primes[i] - modules[i]); - for (; j < gapSize; j += primes[i]) { - isDivisible[j] = true; - } - } - // To execute Miller-Rabin for non-divisible numbers by all first - // primes - for (j = 0; j < gapSize; j++) { - if (!isDivisible[j]) { - probPrime.putCopy(startPoint); - probPrime.addPositiveInt(j); - if (probPrime.isPrime(100)) { - return new BigInteger(probPrime); - } - } - } - startPoint.addPositiveInt(gapSize); - } - } - -} diff --git a/luni/src/main/java/java/math/RoundingMode.java b/luni/src/main/java/java/math/RoundingMode.java deleted file mode 100644 index f4c181eadc..0000000000 --- a/luni/src/main/java/java/math/RoundingMode.java +++ /dev/null @@ -1,122 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package java.math; - -/** - * Specifies the rounding behavior for operations whose results cannot be - * represented exactly. - */ -public enum RoundingMode { - - /** - * Rounding mode where positive values are rounded towards positive infinity - * and negative values towards negative infinity. - * <br> - * Rule: {@code x.round().abs() >= x.abs()} - */ - UP(BigDecimal.ROUND_UP), - - /** - * Rounding mode where the values are rounded towards zero. - * <br> - * Rule: {@code x.round().abs() <= x.abs()} - */ - DOWN(BigDecimal.ROUND_DOWN), - - /** - * Rounding mode to round towards positive infinity. For positive values - * this rounding mode behaves as {@link #UP}, for negative values as - * {@link #DOWN}. - * <br> - * Rule: {@code x.round() >= x} - */ - CEILING(BigDecimal.ROUND_CEILING), - - /** - * Rounding mode to round towards negative infinity. For positive values - * this rounding mode behaves as {@link #DOWN}, for negative values as - * {@link #UP}. - * <br> - * Rule: {@code x.round() <= x} - */ - FLOOR(BigDecimal.ROUND_FLOOR), - - /** - * Rounding mode where values are rounded towards the nearest neighbor. Ties - * are broken by rounding up. - */ - HALF_UP(BigDecimal.ROUND_HALF_UP), - - /** - * Rounding mode where values are rounded towards the nearest neighbor. Ties - * are broken by rounding down. - */ - HALF_DOWN(BigDecimal.ROUND_HALF_DOWN), - - /** - * Rounding mode where values are rounded towards the nearest neighbor. Ties - * are broken by rounding to the even neighbor. - */ - HALF_EVEN(BigDecimal.ROUND_HALF_EVEN), - - /** - * Rounding mode where the rounding operations throws an ArithmeticException - * for the case that rounding is necessary, i.e. for the case that the value - * cannot be represented exactly. - */ - UNNECESSARY(BigDecimal.ROUND_UNNECESSARY); - - /** The old constant of <code>BigDecimal</code>. */ - private final int bigDecimalRM; - - /** It sets the old constant. */ - RoundingMode(int rm) { - bigDecimalRM = rm; - } - - /** - * Converts rounding mode constants from class {@code BigDecimal} into - * {@code RoundingMode} values. - * - * @param mode - * rounding mode constant as defined in class {@code BigDecimal} - * @return corresponding rounding mode object - */ - public static RoundingMode valueOf(int mode) { - switch (mode) { - case BigDecimal.ROUND_CEILING: - return CEILING; - case BigDecimal.ROUND_DOWN: - return DOWN; - case BigDecimal.ROUND_FLOOR: - return FLOOR; - case BigDecimal.ROUND_HALF_DOWN: - return HALF_DOWN; - case BigDecimal.ROUND_HALF_EVEN: - return HALF_EVEN; - case BigDecimal.ROUND_HALF_UP: - return HALF_UP; - case BigDecimal.ROUND_UNNECESSARY: - return UNNECESSARY; - case BigDecimal.ROUND_UP: - return UP; - default: - throw new IllegalArgumentException("Invalid rounding mode"); - } - } -} diff --git a/luni/src/main/java/java/math/TEST_MAPPING b/luni/src/main/java/java/math/TEST_MAPPING deleted file mode 100644 index 1038858691..0000000000 --- a/luni/src/main/java/java/math/TEST_MAPPING +++ /dev/null @@ -1,15 +0,0 @@ -{ - "presubmit": [ - { - "name": "CtsLibcoreTestCases", - "options": [ - { - "include-filter": "org.apache.harmony.tests.java.math" - }, - { - "include-filter": "libcore.java.math" - } - ] - } - ] -}
\ No newline at end of file diff --git a/luni/src/main/java/libcore/math/NativeBN.java b/luni/src/main/java/libcore/math/NativeBN.java new file mode 100644 index 0000000000..fb1cb78a50 --- /dev/null +++ b/luni/src/main/java/libcore/math/NativeBN.java @@ -0,0 +1,54 @@ +/* + * Copyright (C) 2008 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +// TODO: Prune out the methods we no longer need after replacing the BigInteger +// code. + +package libcore.math; + +/** + * @hide + */ +public final class NativeBN { + + public static native long BN_new(); + // BIGNUM *BN_new(void); + + public static native void BN_free(long a); + // void BN_free(BIGNUM *a); + + public static native void litEndInts2bn(int[] ints, int len, boolean neg, long ret); + + // Generates a minimal length representation of |a| in a sequence of integers, least-significant + // word at index 0. + public static native int[] bn2litEndInts(long a); + + public static native int sign(long a); + // Returns -1, 0, 1 AND NOT boolean. + // #define BN_is_negative(a) ((a)->neg != 0) + + public static native void BN_set_negative(long b, int n); + // void BN_set_negative(BIGNUM *b, int n); + + public static native void BN_mul(long r, long a, long b); + // int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); + + public static native void BN_div(long dv, long rem, long num, long divisor); + // int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *num, const BIGNUM *divisor, BN_CTX *ctx); + + public static native void BN_mod_exp(long r, long a, long p, long m); + // int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx); +} diff --git a/luni/src/main/native/Android.bp b/luni/src/main/native/Android.bp index 423cdd11a8..f41e368af8 100644 --- a/luni/src/main/native/Android.bp +++ b/luni/src/main/native/Android.bp @@ -30,7 +30,7 @@ filegroup { "java_lang_StringToReal.cpp", "java_lang_invoke_MethodHandle.cpp", "java_lang_invoke_VarHandle.cpp", - "java_math_NativeBN.cpp", + "libcore_math_NativeBN.cpp", "libcore_icu_ICU.cpp", "libcore_icu_TimeZoneNames.cpp", "libcore_io_AsynchronousCloseMonitor.cpp", diff --git a/luni/src/main/native/Register.cpp b/luni/src/main/native/Register.cpp index 17ca83960c..949d932398 100644 --- a/luni/src/main/native/Register.cpp +++ b/luni/src/main/native/Register.cpp @@ -39,12 +39,12 @@ jint JNI_OnLoad(JavaVM* vm, void*) { // REGISTER(register_java_lang_StringToReal); REGISTER(register_java_lang_invoke_MethodHandle); REGISTER(register_java_lang_invoke_VarHandle); - REGISTER(register_java_math_NativeBN); REGISTER(register_libcore_icu_ICU); REGISTER(register_libcore_icu_TimeZoneNames); REGISTER(register_libcore_io_AsynchronousCloseMonitor); REGISTER(register_libcore_io_Linux); REGISTER(register_libcore_io_Memory); + REGISTER(register_libcore_math_NativeBN); REGISTER(register_libcore_util_NativeAllocationRegistry); REGISTER(register_org_apache_harmony_dalvik_NativeTestTarget); REGISTER(register_org_apache_harmony_xml_ExpatParser); diff --git a/luni/src/main/native/java_math_NativeBN.cpp b/luni/src/main/native/java_math_NativeBN.cpp deleted file mode 100644 index 5d085ec9ec..0000000000 --- a/luni/src/main/native/java_math_NativeBN.cpp +++ /dev/null @@ -1,569 +0,0 @@ -/* - * Copyright (C) 2008 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#define LOG_TAG "NativeBN" - -#include <stdio.h> -#include <algorithm> -#include <memory> - -#include <openssl/bn.h> -#include <openssl/crypto.h> -#include <openssl/err.h> - -#include <nativehelper/JNIHelp.h> -#include <nativehelper/ScopedPrimitiveArray.h> -#include <nativehelper/ScopedUtfChars.h> -#include <nativehelper/jni_macros.h> - -#include "JniException.h" - -struct BN_CTX_Deleter { - void operator()(BN_CTX* p) const { - BN_CTX_free(p); - } -}; -typedef std::unique_ptr<BN_CTX, BN_CTX_Deleter> Unique_BN_CTX; - -static BIGNUM* toBigNum(jlong address) { - return reinterpret_cast<BIGNUM*>(static_cast<uintptr_t>(address)); -} - -static void throwException(JNIEnv* env) { - long error = ERR_get_error(); - // OpenSSL's error queue may contain multiple errors. Clean up after them. - ERR_clear_error(); - - if (error == 0) { - // An operation failed but did not push to the error queue. Throw a default - // exception. - jniThrowException(env, "java/lang/ArithmeticException", "Operation failed"); - return; - } - - char message[256]; - ERR_error_string_n(error, message, sizeof(message)); - int reason = ERR_GET_REASON(error); - if (reason == BN_R_DIV_BY_ZERO) { - jniThrowException(env, "java/lang/ArithmeticException", "BigInteger division by zero"); - } else if (reason == BN_R_NO_INVERSE) { - jniThrowException(env, "java/lang/ArithmeticException", "BigInteger not invertible"); - } else if (reason == ERR_R_MALLOC_FAILURE) { - jniThrowOutOfMemoryError(env, message); - } else { - jniThrowException(env, "java/lang/ArithmeticException", message); - } -} - -static int isValidHandle(JNIEnv* env, jlong handle, const char* message) { - if (handle == 0) { - jniThrowNullPointerException(env, message); - return JNI_FALSE; - } - return JNI_TRUE; -} - -static int oneValidHandle(JNIEnv* env, jlong a) { - return isValidHandle(env, a, "Mandatory handle (first) passed as null"); -} - -static int twoValidHandles(JNIEnv* env, jlong a, jlong b) { - if (!oneValidHandle(env, a)) return JNI_FALSE; - return isValidHandle(env, b, "Mandatory handle (second) passed as null"); -} - -static int threeValidHandles(JNIEnv* env, jlong a, jlong b, jlong c) { - if (!twoValidHandles(env, a, b)) return JNI_FALSE; - return isValidHandle(env, c, "Mandatory handle (third) passed as null"); -} - -static int fourValidHandles(JNIEnv* env, jlong a, jlong b, jlong c, jlong d) { - if (!threeValidHandles(env, a, b, c)) return JNI_FALSE; - return isValidHandle(env, d, "Mandatory handle (fourth) passed as null"); -} - -static jlong NativeBN_BN_new(JNIEnv* env, jclass) { - jlong result = static_cast<jlong>(reinterpret_cast<uintptr_t>(BN_new())); - if (!result) { - throwException(env); - } - return result; -} - -static jlong NativeBN_getNativeFinalizer(JNIEnv*, jclass) { - return static_cast<jlong>(reinterpret_cast<uintptr_t>(&BN_free)); -} - -static void NativeBN_BN_free(JNIEnv* env, jclass, jlong a) { - if (!oneValidHandle(env, a)) return; - BN_free(toBigNum(a)); -} - -static int NativeBN_BN_cmp(JNIEnv* env, jclass, jlong a, jlong b) { - if (!twoValidHandles(env, a, b)) return 1; - return BN_cmp(toBigNum(a), toBigNum(b)); -} - -static void NativeBN_BN_copy(JNIEnv* env, jclass, jlong to, jlong from) { - if (!twoValidHandles(env, to, from)) return; - if (!BN_copy(toBigNum(to), toBigNum(from))) { - throwException(env); - } -} - -static void NativeBN_putULongInt(JNIEnv* env, jclass, jlong a0, jlong java_dw, jboolean neg) { - if (!oneValidHandle(env, a0)) return; - - uint64_t dw = java_dw; - BIGNUM* a = toBigNum(a0); - - if (!BN_set_u64(a, dw)) { - throwException(env); - return; - } - - BN_set_negative(a, neg); -} - -static void NativeBN_putLongInt(JNIEnv* env, jclass cls, jlong a, jlong dw) { - if (dw >= 0) { - NativeBN_putULongInt(env, cls, a, dw, JNI_FALSE); - } else { - NativeBN_putULongInt(env, cls, a, -dw, JNI_TRUE); - } -} - -static int NativeBN_BN_dec2bn(JNIEnv* env, jclass, jlong a0, jstring str) { - if (!oneValidHandle(env, a0)) return -1; - ScopedUtfChars chars(env, str); - if (chars.c_str() == NULL) { - return -1; - } - BIGNUM* a = toBigNum(a0); - int result = BN_dec2bn(&a, chars.c_str()); - if (result == 0) { - throwException(env); - } - return result; -} - -static int NativeBN_BN_hex2bn(JNIEnv* env, jclass, jlong a0, jstring str) { - if (!oneValidHandle(env, a0)) return -1; - ScopedUtfChars chars(env, str); - if (chars.c_str() == NULL) { - return -1; - } - BIGNUM* a = toBigNum(a0); - int result = BN_hex2bn(&a, chars.c_str()); - if (result == 0) { - throwException(env); - } - return result; -} - -static void NativeBN_BN_bin2bn(JNIEnv* env, jclass, jbyteArray arr, int len, jboolean neg, jlong ret) { - if (!oneValidHandle(env, ret)) return; - ScopedByteArrayRO bytes(env, arr); - if (bytes.get() == NULL) { - return; - } - if (!BN_bin2bn(reinterpret_cast<const unsigned char*>(bytes.get()), len, toBigNum(ret))) { - throwException(env); - return; - } - - BN_set_negative(toBigNum(ret), neg); -} - -static void NativeBN_litEndInts2bn(JNIEnv* env, jclass, jintArray arr, int len, jboolean neg, jlong ret0) { - if (!oneValidHandle(env, ret0)) return; - BIGNUM* ret = toBigNum(ret0); - - ScopedIntArrayRO scopedArray(env, arr); - - if (scopedArray.get() == NULL) { - return; - } - - // We can simply interpret the little-endian integer stream as a - // little-endian byte stream and use BN_le2bn. - const uint8_t* tmpBytes = reinterpret_cast<const uint8_t *>(scopedArray.get()); - size_t numBytes = len * sizeof(int); - - if (!BN_le2bn(tmpBytes, numBytes, ret)) { - throwException(env); - } - - BN_set_negative(ret, neg); -} - -static void NativeBN_twosComp2bn(JNIEnv* env, jclass, jbyteArray arr, int bytesLen, jlong ret0) { - if (!oneValidHandle(env, ret0)) return; - BIGNUM* ret = toBigNum(ret0); - - ScopedByteArrayRO bytes(env, arr); - if (bytes.get() == NULL) { - return; - } - - if (bytesLen == 0) { - BN_zero(ret); - return; - } - - const unsigned char* bytesTmp = reinterpret_cast<const unsigned char*>(bytes.get()); - - if (!BN_bin2bn(bytesTmp, bytesLen, ret)) { - throwException(env); - return; - } - - // Use the high bit to determine the sign in twos-complement. - BN_set_negative(ret, (bytes[0] & 0x80) != 0); - - if (BN_is_negative(ret)) { - // For negative values, BN_bin2bn doesn't interpret the twos-complement - // representation, so ret is now (- value - 2^N). We can use nnmod_pow2 to set - // ret to (-value). - if (!BN_nnmod_pow2(ret, ret, bytesLen * 8)) { - throwException(env); - return; - } - - // And now we correct the sign. - BN_set_negative(ret, 1); - } -} - -static jlong NativeBN_longInt(JNIEnv* env, jclass, jlong a0) { - if (!oneValidHandle(env, a0)) return -1; - BIGNUM* a = toBigNum(a0); - uint64_t word; - - if (BN_get_u64(a, &word)) { - return BN_is_negative(a) ? -((jlong) word) : word; - } else { - // This should be unreachable if our caller checks BigInt::twosCompFitsIntoBytes(8) - throwException(env); - return 0; - } -} - -static char* leadingZerosTrimmed(char* s) { - char* p = s; - if (*p == '-') { - p++; - while ((*p == '0') && (*(p + 1) != 0)) { p++; } - p--; - *p = '-'; - } else { - while ((*p == '0') && (*(p + 1) != 0)) { p++; } - } - return p; -} - -static jstring NativeBN_BN_bn2dec(JNIEnv* env, jclass, jlong a) { - if (!oneValidHandle(env, a)) return NULL; - char* tmpStr = BN_bn2dec(toBigNum(a)); - if (tmpStr == NULL) { - throwException(env); - return NULL; - } - char* retStr = leadingZerosTrimmed(tmpStr); - jstring returnJString = env->NewStringUTF(retStr); - OPENSSL_free(tmpStr); - return returnJString; -} - -static jstring NativeBN_BN_bn2hex(JNIEnv* env, jclass, jlong a) { - if (!oneValidHandle(env, a)) return NULL; - char* tmpStr = BN_bn2hex(toBigNum(a)); - if (tmpStr == NULL) { - throwException(env); - return NULL; - } - char* retStr = leadingZerosTrimmed(tmpStr); - jstring returnJString = env->NewStringUTF(retStr); - OPENSSL_free(tmpStr); - return returnJString; -} - -static jbyteArray NativeBN_BN_bn2bin(JNIEnv* env, jclass, jlong a0) { - if (!oneValidHandle(env, a0)) return NULL; - BIGNUM* a = toBigNum(a0); - jbyteArray result = env->NewByteArray(BN_num_bytes(a)); - if (result == NULL) { - return NULL; - } - ScopedByteArrayRW bytes(env, result); - if (bytes.get() == NULL) { - return NULL; - } - BN_bn2bin(a, reinterpret_cast<unsigned char*>(bytes.get())); - return result; -} - -static jintArray NativeBN_bn2litEndInts(JNIEnv* env, jclass, jlong a0) { - if (!oneValidHandle(env, a0)) return NULL; - - BIGNUM* a = toBigNum(a0); - - // The number of integers we need is BN_num_bytes(a) / sizeof(int), rounded up - int intLen = (BN_num_bytes(a) + sizeof(int) - 1) / sizeof(int); - - // Allocate our result with the JNI boilerplate - jintArray result = env->NewIntArray(intLen); - - if (result == NULL) { - throwException(env); - return NULL; - } - - ScopedIntArrayRW ints(env, result); - - unsigned int* uints = reinterpret_cast<unsigned int*>(ints.get()); - if (uints == NULL) { - throwException(env); - return NULL; - } - - // We can simply interpret a little-endian byte stream as a little-endian integer stream. - if (!BN_bn2le_padded(reinterpret_cast<uint8_t*>(uints), intLen * sizeof(int), a)) { - throwException(env); - return NULL; - } - - return result; -} - -static int NativeBN_sign(JNIEnv* env, jclass, jlong a) { - if (!oneValidHandle(env, a)) return -2; - if (BN_is_zero(toBigNum(a))) { - return 0; - } else if (BN_is_negative(toBigNum(a))) { - return -1; - } - return 1; -} - -static void NativeBN_BN_set_negative(JNIEnv* env, jclass, jlong b, int n) { - if (!oneValidHandle(env, b)) return; - BN_set_negative(toBigNum(b), n); -} - -static int NativeBN_bitLength(JNIEnv* env, jclass, jlong a0) { - if (!oneValidHandle(env, a0)) return JNI_FALSE; - BIGNUM* a = toBigNum(a0); - - // If a is not negative, we can use BN_num_bits directly. - if (!BN_is_negative(a)) { - return BN_num_bits(a); - } - - // In the negative case, the number of bits in a is the same as the number of bits in |a|, - // except one less when |a| is a power of two. - BIGNUM positiveA; - BN_init(&positiveA); - - if (!BN_copy(&positiveA, a)) { - BN_free(&positiveA); - throwException(env); - return -1; - } - - BN_set_negative(&positiveA, false); - int numBits = BN_is_pow2(&positiveA) ? BN_num_bits(&positiveA) - 1 : BN_num_bits(&positiveA); - - BN_free(&positiveA); - return numBits; -} - -static jboolean NativeBN_BN_is_bit_set(JNIEnv* env, jclass, jlong a, int n) { - if (!oneValidHandle(env, a)) return JNI_FALSE; - - // NOTE: this is only called in the positive case, so BN_is_bit_set is fine here. - return BN_is_bit_set(toBigNum(a), n) ? JNI_TRUE : JNI_FALSE; -} - -static void NativeBN_BN_shift(JNIEnv* env, jclass, jlong r, jlong a, int n) { - if (!twoValidHandles(env, r, a)) return; - int ok; - if (n >= 0) { - ok = BN_lshift(toBigNum(r), toBigNum(a), n); - } else { - ok = BN_rshift(toBigNum(r), toBigNum(a), -n); - } - if (!ok) { - throwException(env); - } -} - -static void NativeBN_BN_add_word(JNIEnv* env, jclass, jlong a, jint w) { - if (!oneValidHandle(env, a)) return; - if (!BN_add_word(toBigNum(a), w)) { - throwException(env); - } -} - -static void NativeBN_BN_mul_word(JNIEnv* env, jclass, jlong a, jint w) { - if (!oneValidHandle(env, a)) return; - if (!BN_mul_word(toBigNum(a), w)) { - throwException(env); - } -} - -static jint NativeBN_BN_mod_word(JNIEnv* env, jclass, jlong a, jint w) { - if (!oneValidHandle(env, a)) return 0; - BN_ULONG result = BN_mod_word(toBigNum(a), w); - if (result == (BN_ULONG)-1) { - throwException(env); - } - return result; -} - -static void NativeBN_BN_add(JNIEnv* env, jclass, jlong r, jlong a, jlong b) { - if (!threeValidHandles(env, r, a, b)) return; - if (!BN_add(toBigNum(r), toBigNum(a), toBigNum(b))) { - throwException(env); - } -} - -static void NativeBN_BN_sub(JNIEnv* env, jclass, jlong r, jlong a, jlong b) { - if (!threeValidHandles(env, r, a, b)) return; - if (!BN_sub(toBigNum(r), toBigNum(a), toBigNum(b))) { - throwException(env); - } -} - -static void NativeBN_BN_gcd(JNIEnv* env, jclass, jlong r, jlong a, jlong b) { - if (!threeValidHandles(env, r, a, b)) return; - Unique_BN_CTX ctx(BN_CTX_new()); - if (!BN_gcd(toBigNum(r), toBigNum(a), toBigNum(b), ctx.get())) { - throwException(env); - } -} - -static void NativeBN_BN_mul(JNIEnv* env, jclass, jlong r, jlong a, jlong b) { - if (!threeValidHandles(env, r, a, b)) return; - Unique_BN_CTX ctx(BN_CTX_new()); - if (!BN_mul(toBigNum(r), toBigNum(a), toBigNum(b), ctx.get())) { - throwException(env); - } -} - -static void NativeBN_BN_exp(JNIEnv* env, jclass, jlong r, jlong a, jlong p) { - if (!threeValidHandles(env, r, a, p)) return; - Unique_BN_CTX ctx(BN_CTX_new()); - if (!BN_exp(toBigNum(r), toBigNum(a), toBigNum(p), ctx.get())) { - throwException(env); - } -} - -static void NativeBN_BN_div(JNIEnv* env, jclass, jlong dv, jlong rem, jlong m, jlong d) { - if (!fourValidHandles(env, (rem ? rem : dv), (dv ? dv : rem), m, d)) return; - Unique_BN_CTX ctx(BN_CTX_new()); - if (!BN_div(toBigNum(dv), toBigNum(rem), toBigNum(m), toBigNum(d), ctx.get())) { - throwException(env); - } -} - -static void NativeBN_BN_nnmod(JNIEnv* env, jclass, jlong r, jlong a, jlong m) { - if (!threeValidHandles(env, r, a, m)) return; - Unique_BN_CTX ctx(BN_CTX_new()); - if (!BN_nnmod(toBigNum(r), toBigNum(a), toBigNum(m), ctx.get())) { - throwException(env); - } -} - -static void NativeBN_BN_mod_exp(JNIEnv* env, jclass, jlong r, jlong a, jlong p, jlong m) { - if (!fourValidHandles(env, r, a, p, m)) return; - Unique_BN_CTX ctx(BN_CTX_new()); - if (!BN_mod_exp(toBigNum(r), toBigNum(a), toBigNum(p), toBigNum(m), ctx.get())) { - throwException(env); - } -} - -static void NativeBN_BN_mod_inverse(JNIEnv* env, jclass, jlong ret, jlong a, jlong n) { - if (!threeValidHandles(env, ret, a, n)) return; - Unique_BN_CTX ctx(BN_CTX_new()); - if (!BN_mod_inverse(toBigNum(ret), toBigNum(a), toBigNum(n), ctx.get())) { - throwException(env); - } -} - -static void NativeBN_BN_generate_prime_ex(JNIEnv* env, jclass, jlong ret, int bits, - jboolean safe, jlong add, jlong rem) { - if (!oneValidHandle(env, ret)) return; - if (!BN_generate_prime_ex(toBigNum(ret), bits, safe, toBigNum(add), toBigNum(rem), - NULL)) { - throwException(env); - } -} - -static jboolean NativeBN_BN_primality_test(JNIEnv* env, jclass, jlong candidate, int checks, - jboolean do_trial_decryption) { - if (!oneValidHandle(env, candidate)) return JNI_FALSE; - Unique_BN_CTX ctx(BN_CTX_new()); - int is_probably_prime; - if (!BN_primality_test(&is_probably_prime, toBigNum(candidate), checks, ctx.get(), - do_trial_decryption, NULL)) { - throwException(env); - return JNI_FALSE; - } - return is_probably_prime ? JNI_TRUE : JNI_FALSE; -} - -static JNINativeMethod gMethods[] = { - NATIVE_METHOD(NativeBN, BN_add, "(JJJ)V"), - NATIVE_METHOD(NativeBN, BN_add_word, "(JI)V"), - NATIVE_METHOD(NativeBN, BN_bin2bn, "([BIZJ)V"), - NATIVE_METHOD(NativeBN, BN_bn2bin, "(J)[B"), - NATIVE_METHOD(NativeBN, BN_bn2dec, "(J)Ljava/lang/String;"), - NATIVE_METHOD(NativeBN, BN_bn2hex, "(J)Ljava/lang/String;"), - NATIVE_METHOD(NativeBN, BN_cmp, "(JJ)I"), - NATIVE_METHOD(NativeBN, BN_copy, "(JJ)V"), - NATIVE_METHOD(NativeBN, BN_dec2bn, "(JLjava/lang/String;)I"), - NATIVE_METHOD(NativeBN, BN_div, "(JJJJ)V"), - NATIVE_METHOD(NativeBN, BN_exp, "(JJJ)V"), - NATIVE_METHOD(NativeBN, BN_free, "(J)V"), - NATIVE_METHOD(NativeBN, BN_gcd, "(JJJ)V"), - NATIVE_METHOD(NativeBN, BN_generate_prime_ex, "(JIZJJ)V"), - NATIVE_METHOD(NativeBN, BN_hex2bn, "(JLjava/lang/String;)I"), - NATIVE_METHOD(NativeBN, BN_is_bit_set, "(JI)Z"), - NATIVE_METHOD(NativeBN, BN_primality_test, "(JIZ)Z"), - NATIVE_METHOD(NativeBN, BN_mod_exp, "(JJJJ)V"), - NATIVE_METHOD(NativeBN, BN_mod_inverse, "(JJJ)V"), - NATIVE_METHOD(NativeBN, BN_mod_word, "(JI)I"), - NATIVE_METHOD(NativeBN, BN_mul, "(JJJ)V"), - NATIVE_METHOD(NativeBN, BN_mul_word, "(JI)V"), - NATIVE_METHOD(NativeBN, BN_new, "()J"), - NATIVE_METHOD(NativeBN, BN_nnmod, "(JJJ)V"), - NATIVE_METHOD(NativeBN, BN_set_negative, "(JI)V"), - NATIVE_METHOD(NativeBN, BN_shift, "(JJI)V"), - NATIVE_METHOD(NativeBN, BN_sub, "(JJJ)V"), - NATIVE_METHOD(NativeBN, bitLength, "(J)I"), - NATIVE_METHOD(NativeBN, bn2litEndInts, "(J)[I"), - NATIVE_METHOD(NativeBN, getNativeFinalizer, "()J"), - NATIVE_METHOD(NativeBN, litEndInts2bn, "([IIZJ)V"), - NATIVE_METHOD(NativeBN, longInt, "(J)J"), - NATIVE_METHOD(NativeBN, putLongInt, "(JJ)V"), - NATIVE_METHOD(NativeBN, putULongInt, "(JJZ)V"), - NATIVE_METHOD(NativeBN, sign, "(J)I"), - NATIVE_METHOD(NativeBN, twosComp2bn, "([BIJ)V"), -}; -void register_java_math_NativeBN(JNIEnv* env) { - jniRegisterNativeMethods(env, "java/math/NativeBN", gMethods, NELEM(gMethods)); -} diff --git a/luni/src/main/native/libcore_math_NativeBN.cpp b/luni/src/main/native/libcore_math_NativeBN.cpp new file mode 100644 index 0000000000..a123014bc5 --- /dev/null +++ b/luni/src/main/native/libcore_math_NativeBN.cpp @@ -0,0 +1,192 @@ +/* + * Copyright (C) 2008 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +// TODO: Check that we handle context allocation failures correctly. + +#define LOG_TAG "NativeBN" + +#include <stdio.h> +#include <algorithm> +#include <memory> + +#include <openssl/bn.h> +#include <openssl/crypto.h> +#include <openssl/err.h> + +#include <nativehelper/JNIHelp.h> +#include <nativehelper/ScopedPrimitiveArray.h> +#include <nativehelper/ScopedUtfChars.h> +#include <nativehelper/jni_macros.h> + +#include "JniException.h" + +struct BN_CTX_Deleter { + void operator()(BN_CTX* p) const { + BN_CTX_free(p); + } +}; +typedef std::unique_ptr<BN_CTX, BN_CTX_Deleter> Unique_BN_CTX; + +static BIGNUM* toBigNum(jlong address) { + return reinterpret_cast<BIGNUM*>(static_cast<uintptr_t>(address)); +} + +// Exception handling: We follow the usual JNI convention of "throwing" an +// exception if anything goes wrong, and returning junk, typically null. +// The NativeBN_ routines should only be called from Java, or from code +// that immediately returns the result to Java, and thus the +// Java exception should be thrown before we ever see the junk. +// This null BNs should never become visible, and we do not have to deal with +// junk (nulls) as input. +static void throwException(JNIEnv* env) { + long error = ERR_get_error(); + // OpenSSL's error queue may contain multiple errors. Clean up after them. + ERR_clear_error(); + + if (error == 0) { + // An operation failed but did not push to the error queue. Throw a default + // exception. + jniThrowException(env, "java/lang/ArithmeticException", "Operation failed"); + return; + } + + char message[256]; + ERR_error_string_n(error, message, sizeof(message)); + int reason = ERR_GET_REASON(error); + if (reason == BN_R_DIV_BY_ZERO) { + jniThrowException(env, "java/lang/ArithmeticException", "BigInteger division by zero"); + } else if (reason == BN_R_NO_INVERSE) { + jniThrowException(env, "java/lang/ArithmeticException", "BigInteger not invertible"); + } else if (reason == ERR_R_MALLOC_FAILURE) { + jniThrowOutOfMemoryError(env, message); + } else { + jniThrowException(env, "java/lang/ArithmeticException", message); + } +} + +static jlong NativeBN_BN_new(JNIEnv* env, jclass) { + jlong result = static_cast<jlong>(reinterpret_cast<uintptr_t>(BN_new())); + if (!result) { + throwException(env); + } + return result; +} + +static void NativeBN_BN_free(JNIEnv*, jclass, jlong a) { + // Do nothing on a zero argument. + BN_free(toBigNum(a)); +} + +static void NativeBN_litEndInts2bn(JNIEnv* env, jclass, jintArray arr, int len, jboolean neg, jlong ret0) { + BIGNUM* ret = toBigNum(ret0); + + ScopedIntArrayRO scopedArray(env, arr); + + if (scopedArray.get() == NULL) { + return; + } + + // We can simply interpret the little-endian integer stream as a + // little-endian byte stream and use BN_le2bn. + const uint8_t* tmpBytes = reinterpret_cast<const uint8_t *>(scopedArray.get()); + size_t numBytes = len * sizeof(int); + + if (!BN_le2bn(tmpBytes, numBytes, ret)) { + throwException(env); + } + + BN_set_negative(ret, neg); +} + +static jintArray NativeBN_bn2litEndInts(JNIEnv* env, jclass, jlong a0) { + BIGNUM* a = toBigNum(a0); + + // The number of integers we need is BN_num_bytes(a) / sizeof(int), rounded up + int intLen = (BN_num_bytes(a) + sizeof(int) - 1) / sizeof(int); + + // Allocate our result with the JNI boilerplate + jintArray result = env->NewIntArray(intLen); + + if (result == NULL) { + throwException(env); + return NULL; + } + + ScopedIntArrayRW ints(env, result); + + unsigned int* uints = reinterpret_cast<unsigned int*>(ints.get()); + if (uints == NULL) { + throwException(env); + return NULL; + } + + // We can simply interpret a little-endian byte stream as a little-endian integer stream. + if (!BN_bn2le_padded(reinterpret_cast<uint8_t*>(uints), intLen * sizeof(int), a)) { + throwException(env); + return NULL; + } + + return result; +} + +static int NativeBN_sign(JNIEnv*, jclass, jlong a) { + if (BN_is_zero(toBigNum(a))) { + return 0; + } else if (BN_is_negative(toBigNum(a))) { + return -1; + } + return 1; +} + +static void NativeBN_BN_set_negative(JNIEnv*, jclass, jlong b, int n) { + BN_set_negative(toBigNum(b), n); +} + +static void NativeBN_BN_mul(JNIEnv* env, jclass, jlong r, jlong a, jlong b) { + Unique_BN_CTX ctx(BN_CTX_new()); + if (!BN_mul(toBigNum(r), toBigNum(a), toBigNum(b), ctx.get())) { + throwException(env); + } +} + +static void NativeBN_BN_div(JNIEnv* env, jclass, jlong q, jlong rem, jlong num, jlong divisor) { + Unique_BN_CTX ctx(BN_CTX_new()); + if (!BN_div(toBigNum(q), toBigNum(rem), toBigNum(num), toBigNum(divisor), ctx.get())) { + throwException(env); + } +} + +static void NativeBN_BN_mod_exp(JNIEnv* env, jclass, jlong r, jlong a, jlong p, jlong m) { + Unique_BN_CTX ctx(BN_CTX_new()); + if (!BN_mod_exp(toBigNum(r), toBigNum(a), toBigNum(p), toBigNum(m), ctx.get())) { + throwException(env); + } +} + +static JNINativeMethod gMethods[] = { + NATIVE_METHOD(NativeBN, BN_div, "(JJJJ)V"), + NATIVE_METHOD(NativeBN, BN_free, "(J)V"), + NATIVE_METHOD(NativeBN, BN_mod_exp, "(JJJJ)V"), + NATIVE_METHOD(NativeBN, BN_mul, "(JJJ)V"), + NATIVE_METHOD(NativeBN, BN_new, "()J"), + NATIVE_METHOD(NativeBN, BN_set_negative, "(JI)V"), + NATIVE_METHOD(NativeBN, bn2litEndInts, "(J)[I"), + NATIVE_METHOD(NativeBN, litEndInts2bn, "([IIZJ)V"), + NATIVE_METHOD(NativeBN, sign, "(J)I"), +}; +void register_libcore_math_NativeBN(JNIEnv* env) { + jniRegisterNativeMethods(env, "libcore/math/NativeBN", gMethods, NELEM(gMethods)); +} |