1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package java.math; 19 20 // BEGIN android-removed 21 // import org.apache.harmony.math.internal.nls.Messages; 22 // END android-removed 23 24 /** 25 * Static library that provides all operations related with division and modular 26 * arithmetic to {@link BigInteger}. Some methods are provided in both mutable 27 * and immutable way. There are several variants provided listed below: 28 * 29 * <ul type="circle"> 30 * <li> <b>Division</b> 31 * <ul type="circle"> 32 * <li>{@link BigInteger} division and remainder by {@link BigInteger}.</li> 33 * <li>{@link BigInteger} division and remainder by {@code int}.</li> 34 * <li><i>gcd</i> between {@link BigInteger} numbers.</li> 35 * </ul> 36 * </li> 37 * <li> <b>Modular arithmetic </b> 38 * <ul type="circle"> 39 * <li>Modular exponentiation between {@link BigInteger} numbers.</li> 40 * <li>Modular inverse of a {@link BigInteger} numbers.</li> 41 * </ul> 42 * </li> 43 *</ul> 44 */ 45 class Division { 46 47 // BEGIN android-note 48 // The divide method has been dropped since this functionality 49 // is now available from OpenSSL BIGNUM. 50 // END android-note 51 52 /** 53 * Divides an array by an integer value. Implements the Knuth's division 54 * algorithm. See D. Knuth, The Art of Computer Programming, vol. 2. 55 * 56 * @param dest the quotient 57 * @param src the dividend 58 * @param srcLength the length of the dividend 59 * @param divisor the divisor 60 * @return remainder 61 */ 62 static int divideArrayByInt(int dest[], int src[], final int srcLength, 63 final int divisor) { 64 65 long rem = 0; 66 long bLong = divisor & 0xffffffffL; 67 68 for (int i = srcLength - 1; i >= 0; i--) { 69 long temp = (rem << 32) | (src[i] & 0xffffffffL); 70 long quot; 71 if (temp >= 0) { 72 quot = (temp / bLong); 73 rem = (temp % bLong); 74 } else { 75 /* 76 * make the dividend positive shifting it right by 1 bit then 77 * get the quotient an remainder and correct them properly 78 */ 79 long aPos = temp >>> 1; 80 long bPos = divisor >>> 1; 81 quot = aPos / bPos; 82 rem = aPos % bPos; 83 // double the remainder and add 1 if a is odd 84 rem = (rem << 1) + (temp & 1); 85 if ((divisor & 1) != 0) { 86 // the divisor is odd 87 if (quot <= rem) { 88 rem -= quot; 89 } else { 90 if (quot - rem <= bLong) { 91 rem += bLong - quot; 92 quot -= 1; 93 } else { 94 rem += (bLong << 1) - quot; 95 quot -= 2; 96 } 97 } 98 } 99 } 100 dest[i] = (int) (quot & 0xffffffffL); 101 } 102 return (int) rem; 103 } 104 105 /** 106 * Divides an array by an integer value. Implements the Knuth's division 107 * algorithm. See D. Knuth, The Art of Computer Programming, vol. 2. 108 * 109 * @param src the dividend 110 * @param srcLength the length of the dividend 111 * @param divisor the divisor 112 * @return remainder 113 */ 114 static int remainderArrayByInt(int src[], final int srcLength, 115 final int divisor) { 116 117 long result = 0; 118 119 for (int i = srcLength - 1; i >= 0; i--) { 120 long temp = (result << 32) + (src[i] & 0xffffffffL); 121 long res = divideLongByInt(temp, divisor); 122 result = (int) (res >> 32); 123 } 124 return (int) result; 125 } 126 127 /** 128 * Divides a <code>BigInteger</code> by a signed <code>int</code> and 129 * returns the remainder. 130 * 131 * @param dividend the BigInteger to be divided. Must be non-negative. 132 * @param divisor a signed int 133 * @return divide % divisor 134 */ 135 static int remainder(BigInteger dividend, int divisor) { 136 // BEGIN android-added 137 dividend.establishOldRepresentation("Division.remainder"); 138 // END android-added 139 return remainderArrayByInt(dividend.digits, dividend.numberLength, 140 divisor); 141 } 142 143 /** 144 * Divides an unsigned long a by an unsigned int b. It is supposed that the 145 * most significant bit of b is set to 1, i.e. b < 0 146 * 147 * @param a the dividend 148 * @param b the divisor 149 * @return the long value containing the unsigned integer remainder in the 150 * left half and the unsigned integer quotient in the right half 151 */ 152 static long divideLongByInt(long a, int b) { 153 long quot; 154 long rem; 155 long bLong = b & 0xffffffffL; 156 157 if (a >= 0) { 158 quot = (a / bLong); 159 rem = (a % bLong); 160 } else { 161 /* 162 * Make the dividend positive shifting it right by 1 bit then get 163 * the quotient an remainder and correct them properly 164 */ 165 long aPos = a >>> 1; 166 long bPos = b >>> 1; 167 quot = aPos / bPos; 168 rem = aPos % bPos; 169 // double the remainder and add 1 if a is odd 170 rem = (rem << 1) + (a & 1); 171 if ((b & 1) != 0) { // the divisor is odd 172 if (quot <= rem) { 173 rem -= quot; 174 } else { 175 if (quot - rem <= bLong) { 176 rem += bLong - quot; 177 quot -= 1; 178 } else { 179 rem += (bLong << 1) - quot; 180 quot -= 2; 181 } 182 } 183 } 184 } 185 return (rem << 32) | (quot & 0xffffffffL); 186 } 187 188 /** 189 * Computes the quotient and the remainder after a division by an {@code int} 190 * number. 191 * 192 * @return an array of the form {@code [quotient, remainder]}. 193 */ 194 static BigInteger[] divideAndRemainderByInteger(BigInteger val, 195 int divisor, int divisorSign) { 196 // BEGIN android-added 197 val.establishOldRepresentation("Division.divideAndRemainderByInteger"); 198 // END android-added 199 // res[0] is a quotient and res[1] is a remainder: 200 int[] valDigits = val.digits; 201 int valLen = val.numberLength; 202 int valSign = val.sign; 203 if (valLen == 1) { 204 long a = (valDigits[0] & 0xffffffffL); 205 long b = (divisor & 0xffffffffL); 206 long quo = a / b; 207 long rem = a % b; 208 if (valSign != divisorSign) { 209 quo = -quo; 210 } 211 if (valSign < 0) { 212 rem = -rem; 213 } 214 return new BigInteger[] { BigInteger.valueOf(quo), 215 BigInteger.valueOf(rem) }; 216 } 217 int quotientLength = valLen; 218 int quotientSign = ((valSign == divisorSign) ? 1 : -1); 219 int quotientDigits[] = new int[quotientLength]; 220 int remainderDigits[]; 221 remainderDigits = new int[] { Division.divideArrayByInt( 222 quotientDigits, valDigits, valLen, divisor) }; 223 BigInteger result0 = new BigInteger(quotientSign, quotientLength, 224 quotientDigits); 225 BigInteger result1 = new BigInteger(valSign, 1, remainderDigits); 226 result0.cutOffLeadingZeroes(); 227 result1.cutOffLeadingZeroes(); 228 return new BigInteger[] { result0, result1 }; 229 } 230 231 // BEGIN android-note 232 // A big part of this class that only has been used by the divide method 233 // has been dropped in favor of using the BIGNUM impl. 234 // END android-note 235 } 236
