harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From telli...@apache.org
Subject 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
Date Wed, 18 Jun 2008 12:45:23 GMT
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);
+    }
+
 }



Mime
View raw message