You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by te...@apache.org on 2008/06/18 14:45:23 UTC
svn commit: r669154 - in
/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math:
BigDecimal.java BigInteger.java BitLevel.java Division.java
Multiplication.java
Author: tellison
Date: Wed Jun 18 05:45:23 2008
New Revision: 669154
URL: http://svn.apache.org/viewvc?rev=669154&view=rev
Log:
Apply patch HARMONY-5825 ([classlib][math] RSA-related performance optimization)
Modified:
harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java
harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java
harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java
harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java
harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Multiplication.java
Modified: harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java?rev=669154&r1=669153&r2=669154&view=diff
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java (original)
+++ harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java Wed Jun 18 05:45:23 2008
@@ -743,7 +743,7 @@
} else {
// Checking if: remainder * 2 >= scaledDivisor
- compRem = remainder.abs().shiftLeft(1).compareTo(scaledDivisor.abs());
+ compRem = remainder.abs().shiftLeftOneBit().compareTo(scaledDivisor.abs());
compRem = roundingBehavior(quotient.testBit(0) ? 1 : 0,
sign * (5 + compRem), roundingMode);
}
@@ -875,7 +875,7 @@
// Calculating the exact quotient with at least 'mc.precision()' digits
if (quotAndRem[1].signum() != 0) {
// Checking if: 2 * remainder >= divisor ?
- compRem = quotAndRem[1].shiftLeft(1).compareTo( divisor.getUnscaledValue() );
+ 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)));
@@ -1691,7 +1691,7 @@
// Computing (mantisa * 2^k) / 10^s
quotAndRem = mantisa.divideAndRemainder(powerOfTen);
// To check if the fractional part >= 0.5
- compRem = quotAndRem[1].shiftLeft(1).compareTo(powerOfTen);
+ compRem = quotAndRem[1].shiftLeftOneBit().compareTo(powerOfTen);
// To add two rounded bits at end of mantisa
mantisa = quotAndRem[0].shiftLeft(2).add(
BigInteger.valueOf((compRem * (compRem + 3)) / 2 + 1));
@@ -1791,7 +1791,7 @@
// 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().shiftLeft(1).compareTo(sizeOfFraction));
+ 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),
Modified: harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java?rev=669154&r1=669153&r2=669154&view=diff
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java (original)
+++ harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java Wed Jun 18 05:45:23 2008
@@ -65,6 +65,15 @@
new BigInteger(1, 6), new BigInteger(1, 7), new BigInteger(1, 8),
new BigInteger(1, 9), TEN };
+ static final BigInteger[] TWO_POWS;
+
+ static {
+ TWO_POWS = new BigInteger[32];
+ for(int i = 0; i < TWO_POWS.length; i++) {
+ TWO_POWS[i] = BigInteger.valueOf(1L<<i);
+ }
+ }
+
private transient int firstNonzeroDigit = -2;
/* Serialized Fields */
@@ -423,6 +432,10 @@
this, -n));
}
+ BigInteger shiftLeftOneBit() {
+ return (sign == 0) ? this : BitLevel.shiftLeftOneBit(this);
+ }
+
public int bitLength() {
return BitLevel.bitLength(this);
}
@@ -647,12 +660,10 @@
// calculate by shifting.
if (!testBit(0)) {
int x = 1;
- BigInteger factor = BigInteger.ONE.shiftLeft(exp);
while (!testBit(x)) {
- factor = factor.shiftLeft(exp);
x++;
}
- return factor.multiply(this.shiftRight(x).pow(exp));
+ return getPowerOfTwo(x*exp).multiply(this.shiftRight(x).pow(exp));
}
return Multiplication.pow(this, exp);
}
@@ -971,4 +982,16 @@
void unCache() {
firstNonzeroDigit = -2;
}
+
+ static BigInteger getPowerOfTwo(int exp) {
+ if(exp < TWO_POWS.length) {
+ return TWO_POWS[exp];
+ }
+ int intCount = exp >> 5;
+ int bitN = exp & 31;
+ int resDigits[] = new int[intCount+1];
+ resDigits[intCount] = 1 << bitN;
+ return new BigInteger(1, intCount+1, resDigits);
+ }
}
+
Modified: harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java?rev=669154&r1=669153&r2=669154&view=diff
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java (original)
+++ harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java Wed Jun 18 05:45:23 2008
@@ -169,6 +169,28 @@
}
}
+ 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) {
+ int srcLen = source.numberLength;
+ int resLen = srcLen + 1;
+ int resDigits[] = new int[resLen];
+ shiftLeftOneBit(resDigits, source.digits, srcLen);
+ BigInteger result = new BigInteger(source.sign, resLen, resDigits);
+ result.cutOffLeadingZeroes();
+ return result;
+ }
+
/** @see BigInteger#shiftRight(int) */
static BigInteger shiftRight(BigInteger source, int count) {
int intCount = count >> 5; // count of integers
Modified: harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java?rev=669154&r1=669153&r2=669154&view=diff
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java (original)
+++ harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java Wed Jun 18 05:45:23 2008
@@ -136,7 +136,7 @@
if (guessDigit != 0) {
int borrow = Division.multiplyAndSubtract(normA, j
- normBLength, normB, normBLength,
- guessDigit & 0xffffffffL);
+ guessDigit);
// Step D5: check the borrow
if (borrow != 0) {
// Step D6: compensating addition
@@ -353,29 +353,21 @@
* @param c the multiplier of b
* @return the carry element of subtraction
*/
- static int multiplyAndSubtract(int a[], int start, int b[], int bLen, long c) {
- int i;
- int carry = 0;
- long product;
- int productInt;
-
- for (i = 0; i < bLen; i++) {
- product = c * (b[i] & 0xffffffffL);
- productInt = (int) product;
- productInt += carry;
- carry = (int) (product >> 32)
- + ((productInt ^ 0x80000000) < (carry ^ 0x80000000) ? 1 : 0);
- productInt = a[start + i] - productInt;
- if ((productInt ^ 0x80000000) > (a[start + i] ^ 0x80000000)) {
- carry++;
- }
- a[start + i] = productInt;
- }
- product = (a[start + i] & 0xffffffffL)
- - (carry & 0xffffffffL);
- a[start + i] = (int) product;
- carry = (int) (product >> 32); // -1 or 0
- return carry;
+ static int multiplyAndSubtract(int a[], int start, int b[], int bLen, int c) {
+ long carry0 = 0;
+ long carry1 = 0;
+
+ for (int i = 0; i < bLen; i++) {
+ carry0 = Multiplication.unsignedMultAddAdd(b[i], c, (int)carry0, 0);
+ carry1 = (a[start+i] & 0xffffffffL) - (carry0 & 0xffffffffL) + carry1;
+ a[start+i] = (int)carry1;
+ carry1 >>= 32; // -1 or 0
+ carry0 >>>= 32;
+ }
+
+ carry1 = (a[start + bLen] & 0xffffffffL) - carry0 + carry1;
+ a[start + bLen] = (int)carry1;
+ return (int)(carry1 >> 32); // -1 or 0
}
/**
@@ -503,52 +495,10 @@
}
int m = p.numberLength * 32;
-
- Object[] save = almostMonInv(a, p);
- BigInteger r = ( (BigInteger) save[0] );
- int k = ( (Integer) save[1] ).intValue();
-// assert ( k >= n && k <= m + n );
-
- long n1 = calcN(p);
-
- if (k > m) {
- r = monPro(r, BigInteger.ONE, p, n1);
- k = k - m;
-// assert k < m;
- }
- r = monPro(r, BigInteger.ONE.shiftLeft(m - k), p, n1);
- return r;
- }
-
- /**
- * Calculate the first digit of the inverse
- */
- private static long calcN(BigInteger a) {
- long m0 = a.digits[0] & 0xFFFFFFFFL;
- long n2 = 1L; // this is a'[0]
- long powerOfTwo = 2L;
-
- do {
- if (( ( m0 * n2 ) & powerOfTwo ) != 0) {
- n2 |= powerOfTwo;
- }
- powerOfTwo <<= 1;
- } while (powerOfTwo < 0x100000000L);
- n2 = -n2;
- return n2;
- }
-
- /**
- * Used for an intermediate result of the modInverse algorithm
- * @return the pair: ((BigInteger)r, (Integer)k) where r == a^(-1) * 2^k mod (module)
- */
- private static Object[] almostMonInv(BigInteger a, BigInteger module) {
// PRE: a \in [1, p - 1]
BigInteger u, v, r, s;
- // make copy to use inplace method
- u = module.copy();
+ u = p.copy(); // make copy to use inplace method
v = a.copy();
-
int max = Math.max(v.numberLength, u.numberLength);
r = new BigInteger(1, 1, new int[max + 1]);
s = new BigInteger(1, 1, new int[max + 1]);
@@ -571,9 +521,8 @@
BitLevel.inplaceShiftRight(v, lsbv);
BitLevel.inplaceShiftLeft(s, lsbu);
k += lsbv - lsbu;
-
- }
-
+ }
+
r.sign = 1;
while (v.signum() > 0) {
// INV v >= 0, u >= 0, v odd, u odd (except last iteration when v is even (0))
@@ -584,8 +533,7 @@
BitLevel.inplaceShiftRight(u, toShift);
Elementary.inplaceAdd(r, s);
BitLevel.inplaceShiftLeft(s, toShift);
- k += toShift;
-
+ k += toShift;
}
while (u.compareTo(v) <= BigInteger.EQUALS) {
@@ -597,25 +545,48 @@
Elementary.inplaceAdd(s, r);
BitLevel.inplaceShiftLeft(r, toShift);
k += toShift;
-
}
-
}
if (!u.isOne()){
// in u is stored the gcd
// math.19: BigInteger not invertible.
throw new ArithmeticException(Messages.getString("math.19"));
}
+ if (r.compareTo(p) >= BigInteger.EQUALS) {
+ Elementary.inplaceSubtract(r, p);
+ }
- if (r.compareTo(module) >= BigInteger.EQUALS) {
- Elementary.inplaceSubtract(r, module);
+ r = p.subtract(r);
+
+ // Have pair: ((BigInteger)r, (Integer)k) where r == a^(-1) * 2^k mod (module)
+ int n1 = calcN(p);
+ if (k > m) {
+ r = monPro(r, BigInteger.ONE, p, n1);
+ k = k - m;
}
- r = module.subtract(r);
- return new Object[] { r, k };
+ r = monPro(r, BigInteger.getPowerOfTwo(m - k), p, n1);
+ return r;
}
/**
+ * Calculate the first digit of the inverse
+ */
+ private static int calcN(BigInteger a) {
+ long m0 = a.digits[0] & 0xFFFFFFFFL;
+ long n2 = 1L; // this is a'[0]
+ long powerOfTwo = 2L;
+ do {
+ if (((m0 * n2) & powerOfTwo) != 0) {
+ n2 |= powerOfTwo;
+ }
+ powerOfTwo <<= 1;
+ } while (powerOfTwo < 0x100000000L);
+ n2 = -n2;
+ return (int)(n2 & 0xFFFFFFFFL);
+ }
+
+ /**
* @return bi == abs(2^exp)
*/
private static boolean isPowerOfTwo(BigInteger bi, int exp) {
@@ -754,7 +725,7 @@
return r;
}
- static BigInteger squareAndMultiply(BigInteger x2, BigInteger a2, BigInteger exponent,BigInteger modulus, long n2 ){
+ static BigInteger squareAndMultiply(BigInteger x2, BigInteger a2, BigInteger exponent,BigInteger modulus, int n2 ){
BigInteger res = x2;
for (int i = exponent.bitLength() - 1; i >= 0; i--) {
res = monPro(res,res,modulus, n2);
@@ -771,7 +742,7 @@
*@see #oddModPow(BigInteger, BigInteger,
* BigInteger)
*/
- static BigInteger slidingWindow(BigInteger x2, BigInteger a2, BigInteger exponent,BigInteger modulus, long n2){
+ static BigInteger slidingWindow(BigInteger x2, BigInteger a2, BigInteger exponent,BigInteger modulus, int n2){
// fill odd low pows of a2
BigInteger pows[] = new BigInteger[8];
BigInteger res = x2;
@@ -780,7 +751,7 @@
int acc3;
pows[0] = a2;
- x3 = monSquare(a2,modulus,n2);
+ x3 = monPro(a2,a2,modulus,n2);
for (int i = 1; i <= 7; i++){
pows[i] = monPro(pows[i-1],x3,modulus,n2) ;
}
@@ -802,12 +773,12 @@
}
for(int j = acc3; j <= i; j++) {
- res = monSquare(res,modulus,n2);
+ res = monPro(res,res,modulus,n2);
}
res = monPro(pows[(lowexp-1)>>1], res, modulus,n2);
i = acc3 ;
}else{
- res = monSquare(res, modulus, n2) ;
+ res = monPro(res, res, modulus, n2) ;
}
}
return res;
@@ -818,11 +789,11 @@
* requires that all parameters be positive and the modulus be odd. >
*
* @see BigInteger#modPow(BigInteger, BigInteger)
- * @see #monPro(BigInteger, BigInteger, BigInteger, long)
+ * @see #monPro(BigInteger, BigInteger, BigInteger, int)
* @see #slidingWindow(BigInteger, BigInteger, BigInteger, BigInteger,
- * long)
+ * int)
* @see #squareAndMultiply(BigInteger, BigInteger, BigInteger, BigInteger,
- * long)
+ * int)
*/
static BigInteger oddModPow(BigInteger base, BigInteger exponent,
BigInteger modulus) {
@@ -831,22 +802,11 @@
// n-residue of base [base * r (mod modulus)]
BigInteger a2 = base.shiftLeft(k).mod(modulus);
// n-residue of base [1 * r (mod modulus)]
- BigInteger x2 = BigInteger.ZERO.setBit(k).mod(modulus);
+ BigInteger x2 = BigInteger.getPowerOfTwo(k).mod(modulus);
BigInteger res;
// Compute (modulus[0]^(-1)) (mod 2^32) for odd modulus
- long m0 = modulus.digits[0] & 0xFFFFFFFFL;
- long n2 = 1L; // this is n'[0]
- long powerOfTwo = 2L;
- // compute n2
- do {
- if (((m0 * n2) & powerOfTwo) != 0) {
- n2 |= powerOfTwo;
- }
- powerOfTwo <<= 1;
- } while (powerOfTwo < 0x100000000L);
- n2 = -n2;
-
+ int n2 = calcN(modulus);
if( modulus.numberLength == 1 ){
res = squareAndMultiply(x2,a2, exponent, modulus,n2);
} else {
@@ -884,7 +844,7 @@
BigInteger y = (x2.subtract(x1)).multiply(qInv);
inplaceModPow2(y, j);
if (y.sign < 0) {
- y = y.add(BigInteger.ZERO.setBit(j));
+ y = y.add(BigInteger.getPowerOfTwo(j));
}
// STEP 5: Compute and return: x1 + q * y
return x1.add(q.multiply(y));
@@ -924,75 +884,33 @@
return res;
}
- /** Implements the Montgomery Square of a BigInteger.
- * @see #monPro(BigInteger, BigInteger, BigInteger,
- * long)
- */
- static BigInteger monSquare(BigInteger aBig, BigInteger modulus,
- long n2){
- if(modulus.numberLength == 1){
- return monPro(aBig, aBig, modulus, n2);
- }
- //Squaring
- int [] a = aBig.digits;
- int [] n = modulus.digits;
- int s = modulus.numberLength;
-
- //Multiplying...
- int [] t = new int [(s<<1) + 1];
- long cs;
-
- int limit = Math.min(s,aBig.numberLength );
- for(int i=0; i<limit; i++){
- cs = 0;
- for (int j=i+1; j<limit; j++){
- cs += (0xFFFFFFFFL & t[i+j]) + (0xFFFFFFFFL & a[i]) * (0xFFFFFFFFL & a[j]) ;
- t[i+j] = (int) cs;
- cs >>>= 32;
+ private static void monReduction(int[] res, BigInteger modulus, int n2) {
+
+ /* res + m*modulus_digits */
+ int[] modulus_digits = modulus.digits;
+ int modulusLen = modulus.numberLength;
+ long outerCarry = 0;
+
+ for (int i = 0; i < modulusLen; i++){
+ long innnerCarry = 0;
+ int m = (int) Multiplication.unsignedMultAddAdd(res[i],n2,0,0);
+ for(int j = 0; j < modulusLen; j++){
+ innnerCarry = Multiplication.unsignedMultAddAdd(m, modulus_digits[j], res[i+j], (int)innnerCarry);
+ res[i+j] = (int) innnerCarry;
+ innnerCarry >>>= 32;
}
-
- t[i+limit] = (int) cs;
+
+ outerCarry += (res[i+modulusLen] & 0xFFFFFFFFL) + innnerCarry;
+ res[i+modulusLen] = (int) outerCarry;
+ outerCarry >>>= 32;
}
- BitLevel.shiftLeft( t, t, 0, 1 );
- cs = 0;
- long carry = 0;
- for(int i=0, index = 0; i< s; i++, index++){
- cs += (0xFFFFFFFFL & a[i]) * (0xFFFFFFFFL & a[i]) + (t[index] & 0xFFFFFFFFL);
- t[index] = (int) cs;
- cs >>>= 32;
- index++;
- cs += t[index] & 0xFFFFFFFFL ;
- t[index] = (int)cs;
- cs >>>= 32;
- }
-
- //Reducing...
- /* t + m*n */
- int m = 0;
- int i, j;
- cs = carry = 0;
- for (i=0; i<s; i++){
- cs = 0;
- m = (int) ((t[i] & 0xFFFFFFFFL) * (n2 & 0xFFFFFFFFL));
- for(j=0; j<s; j++){
- cs = (t[i+j] & 0xFFFFFFFFL) + (m & 0xFFFFFFFFL) * (n[j] & 0xFFFFFFFFL) + (cs >>> 32);
- t[i+j] = (int) cs;
- }
- //Adding C to the result
- carry += (t[i+s] & 0xFFFFFFFFL) + ( (cs>>>32) & 0xFFFFFFFFL);
- t[i+s] = (int) carry;
- carry >>>=32;
- }
-
- t[s<<1] = (int) carry;
-
- /* t / r */
- for(j=0; j<s+1; j++){
- t[j] = t[j+s];
+ res[modulusLen << 1] = (int) outerCarry;
+
+ /* res / r */
+ for(int j = 0; j < modulusLen+1; j++){
+ res[j] = res[j+modulusLen];
}
- /*step 3*/
- return finalSubtraction(t, s, s, modulus );
}
/**
@@ -1008,82 +926,46 @@
* Multiplication Algorithms"
* @see #modPowOdd(BigInteger, BigInteger, BigInteger)
*/
- static BigInteger monPro(BigInteger a, BigInteger b, BigInteger modulus,
- long n2) {
- int aFirst = a.numberLength - 1;
- int bFirst = b.numberLength - 1;
- int s = modulus.numberLength;
- int n[] = modulus.digits;
-
- int m;
- int i, j;
- int t[] = new int[(s << 1) + 1];
- long product;
- long C;
- long aI;
-
- for (i = 0; i < s; i++) {
- C = 0;
- aI = (i > aFirst) ? 0 : (a.digits[i] & 0xFFFFFFFFL);
- for (j = 0; j < s; j++) {
- product = (t[j] & 0xFFFFFFFFL) + C
- + ((j > bFirst) ? 0 : (b.digits[j] & 0xFFFFFFFFL) * aI);
- C = product >>> 32;
- t[j] = (int) product;
- }
- product = (t[s] & 0xFFFFFFFFL) + C;
- C = product >>> 32;
- t[s] = (int) product;
- t[s + 1] = (int) C;
-
- m = (int) ((t[0] & 0xFFFFFFFFL) * n2);
- product = (t[0] & 0xFFFFFFFFL) + (m & 0xFFFFFFFFL)
- * (n[0] & 0xFFFFFFFFL);
- C = (int) (product >>> 32);
- for (j = 1; j < s; j++) {
- product = (t[j] & 0xFFFFFFFFL) + (C & 0xFFFFFFFFL)
- + (m & 0xFFFFFFFFL) * (n[j] & 0xFFFFFFFFL);
- C = product >>> 32;
- t[j - 1] = (int) product;
- }
- product = (t[s] & 0xFFFFFFFFL) + (C & 0xFFFFFFFFL);
- C = product >>> 32;
- t[s - 1] = (int) product;
- t[s] = t[s + 1] + (int) C;
- }
-
- return finalSubtraction(t, t.length-1 ,s, modulus);
-
- }
- /*Performs the final reduction of the Montgomery algorithm.
- *@see monPro(BigInteger, BigInteger, BigInteger,
- *long )
- *@see monSquare(BigInteger, BigInteger ,
- *long)
+ static BigInteger monPro(BigInteger a, BigInteger b, BigInteger modulus, int n2) {
+ int modulusLen = modulus.numberLength;
+ int res[] = new int[(modulusLen << 1) + 1];
+ Multiplication.multArraysPAP(a.digits, Math.min(modulusLen, a.numberLength),
+ b.digits, Math.min(modulusLen, b.numberLength), res);
+ monReduction(res,modulus,n2);
+ return finalSubtraction(res, modulus);
+
+ }
+
+ /**
+ * Performs the final reduction of the Montgomery algorithm.
+ * @see monPro(BigInteger, BigInteger, BigInteger, long)
+ * @see monSquare(BigInteger, BigInteger, long)
*/
- static BigInteger finalSubtraction(int t[], int tLength ,int s, BigInteger modulus){
+ static BigInteger finalSubtraction(int res[], BigInteger modulus){
+
// skipping leading zeros
- int i;
- int n[] = modulus.digits;
- boolean lower = false;
-
- for (i = tLength; (i > 0) && (t[i] == 0); i--)
- ;
-
- if (i == s - 1) {
- for (; (i >= 0) && (t[i] == n[i]); i--)
- ;
- lower = (i >= 0) && (t[i] & 0xFFFFFFFFL) < (n[i] & 0xFFFFFFFFL);
- } else {
- lower = (i < s - 1);
+ int modulusLen = modulus.numberLength;
+ boolean doSub = res[modulusLen]!=0;
+ if(!doSub) {
+ int modulusDigits[] = modulus.digits;
+ doSub = true;
+ for(int i = modulusLen - 1; i >= 0; i--) {
+ if(res[i] != modulusDigits[i]) {
+ doSub = (res[i] != 0) && ((res[i] & 0xFFFFFFFFL) > (modulusDigits[i] & 0xFFFFFFFFL));
+ break;
+ }
+ }
}
- BigInteger res = new BigInteger(1, s+1, t);
- // if (t >= n) compute (t - n)
- if (!lower) {
- Elementary.inplaceSubtract(res, modulus);
+
+ BigInteger result = new BigInteger(1, modulusLen+1, res);
+
+ // if (res >= modulusDigits) compute (res - modulusDigits)
+ if (doSub) {
+ Elementary.inplaceSubtract(result, modulus);
}
- res.cutOffLeadingZeroes();
- return res;
+
+ result.cutOffLeadingZeroes();
+ return result;
}
/**
Modified: harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Multiplication.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Multiplication.java?rev=669154&r1=669153&r2=669154&view=diff
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Multiplication.java (original)
+++ harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Multiplication.java Wed Jun 18 05:45:23 2008
@@ -233,8 +233,7 @@
int resSign = (a.sign != b.sign) ? -1 : 1;
// A special case when both numbers don't exceed int
if (resLength == 2) {
- long val = (a.digits[0] & 0xFFFFFFFFL)
- * (b.digits[0] & 0xFFFFFFFFL);
+ long val = unsignedMultAddAdd(a.digits[0], b.digits[0], 0, 0);
int valueLo = (int)val;
int valueHi = (int)(val >>> 32);
return ((valueHi == 0)
@@ -244,27 +243,43 @@
int[] aDigits = a.digits;
int[] bDigits = b.digits;
int resDigits[] = new int[resLength];
- long carry;
- long bDigit;
- int i, j, m;
// Common case
- for (j = 0; j < bLen; j++) {
- carry = 0;
- bDigit = (bDigits[j] & 0xFFFFFFFFL);
- for (i = 0, m = j; i < aLen; i++, m++) {
- carry += (aDigits[i] & 0xFFFFFFFFL)
- * bDigit
- + (resDigits[m] & 0xFFFFFFFFL);
- resDigits[m] = (int)carry;
- carry >>>= 32;
- }
- resDigits[m] = (int) carry;
- }
+ multArraysPAP(aDigits, aLen, bDigits, bLen, resDigits);
BigInteger result = new BigInteger(resSign, resLength, resDigits);
result.cutOffLeadingZeroes();
return result;
}
+ static void multArraysPAP(int[] aDigits, int aLen, int[] bDigits, int bLen, int[] resDigits) {
+ if(aLen == 0 || bLen == 0) return;
+
+ if(aLen == 1) {
+ resDigits[bLen] = multiplyByInt(resDigits, bDigits, bLen, aDigits[0]);
+ } else if(bLen == 1) {
+ resDigits[aLen] = multiplyByInt(resDigits, aDigits, aLen, bDigits[0]);
+ } else {
+ multPAP(aDigits, bDigits, resDigits, aLen, bLen);
+ }
+ }
+
+ static void multPAP(int a[], int b[], int t[], int aLen, int bLen) {
+ if(a == b && aLen == bLen) {
+ square(a, aLen, t);
+ return;
+ }
+
+ for(int i = 0; i < aLen; i++){
+ long carry = 0;
+ int aI = a[i];
+ for (int j = 0; j < bLen; j++){
+ carry = unsignedMultAddAdd(aI, b[j], t[i+j], (int)carry);
+ t[i+j] = (int) carry;
+ carry >>>= 32;
+ }
+ t[i+bLen] = (int) carry;
+ }
+ }
+
/**
* Multiplies an array of integers by an integer value
* and saves the result in {@code res}.
@@ -275,9 +290,8 @@
*/
private static int multiplyByInt(int res[], int a[], final int aSize, final int factor) {
long carry = 0;
-
for (int i = 0; i < aSize; i++) {
- carry += (a[i] & 0xFFFFFFFFL) * (factor & 0xFFFFFFFFL);
+ carry = unsignedMultAddAdd(a[i], factor, (int)carry, 0);
res[i] = (int)carry;
carry >>>= 32;
}
@@ -311,7 +325,7 @@
int[] aDigits = val.digits;
if (aNumberLength == 1) {
- long res = (aDigits[0] & 0xFFFFFFFFL) * (factor);
+ long res = unsignedMultAddAdd(aDigits[0], factor, 0, 0);
int resLo = (int)res;
int resHi = (int)(res >>> 32);
return ((resHi == 0)
@@ -344,7 +358,7 @@
acc = acc.multiply(acc); // square
}
else{
- acc = new BigInteger(1, square(acc.digits, acc.numberLength));
+ acc = new BigInteger(1, square(acc.digits, acc.numberLength, new int [acc.numberLength<<1]));
}
}
// exponent == 1, multiply one more time
@@ -355,37 +369,34 @@
/**
* Performs a<sup>2</sup>
* @param a The number to square.
- * @param length The length of the number to square.
+ * @param aLen The length of the number to square.
*/
- static int[] square(int[] a, int s) {
- int [] t = new int [s<<1];
- long cs;
- long aI;
- for(int i=0; i<s; i++){
- cs = 0;
- aI = (0xFFFFFFFFL & a[i]);
- for (int j=i+1; j<s; j++){
- cs += (0xFFFFFFFFL & t[i+j]) + aI * (0xFFFFFFFFL & a[j]) ;
- t[i+j] = (int) cs;
- cs >>>= 32;
+ static int[] square(int[] a, int aLen, int[] res) {
+ long carry;
+
+ for(int i = 0; i < aLen; i++){
+ carry = 0;
+ for (int j = i+1; j < aLen; j++){
+ carry = unsignedMultAddAdd(a[i], a[j], res[i+j], (int)carry);
+ res[i+j] = (int) carry;
+ carry >>>= 32;
}
-
- t[i+s] = (int) cs;
+ res[i+aLen] = (int) carry;
}
- BitLevel.shiftLeft( t, t, 0, 1 );
- cs = 0;
- for(int i=0, index = 0; i< s; i++, index++){
- aI = (0xFFFFFFFFL & a[i]);
- cs += aI * aI + (t[index] & 0xFFFFFFFFL);
- t[index] = (int) cs;
- cs >>>= 32;
+ BitLevel.shiftLeftOneBit(res, res, aLen << 1);
+
+ carry = 0;
+ for(int i = 0, index = 0; i < aLen; i++, index++){
+ carry = unsignedMultAddAdd(a[i], a[i], res[index],(int)carry);
+ res[index] = (int) carry;
+ carry >>>= 32;
index++;
- cs += t[index] & 0xFFFFFFFFL ;
- t[index] = (int)cs;
- cs >>>= 32;
+ carry += res[index] & 0xFFFFFFFFL;
+ res[index] = (int)carry;
+ carry >>>= 32;
}
- return t;
+ return res;
}
/**
@@ -483,4 +494,23 @@
return val.multiply(bigFivePows[1].pow(exp));
}
}
+
+ /**
+ * Computes the value unsigned ((uint)a*(uint)b + (uint)c + (uint)d). This
+ * method could improve the readability and performance of the code.
+ *
+ * @param a
+ * parameter 1
+ * @param b
+ * parameter 2
+ * @param c
+ * parameter 3
+ * @param d
+ * parameter 4
+ * @return value of expression
+ */
+ static long unsignedMultAddAdd(int a, int b, int c, int d) {
+ return (a & 0xFFFFFFFFL) * (b & 0xFFFFFFFFL) + (c & 0xFFFFFFFFL) + (d & 0xFFFFFFFFL);
+ }
+
}