248 * The threshold value for using Schoenhage recursive base conversion. If
249 * the number of ints in the number are larger than this value,
250 * the Schoenhage algorithm will be used. In practice, it appears that the
251 * Schoenhage routine is faster for any threshold down to 2, and is
252 * relatively flat for thresholds between 2-25, so this choice may be
253 * varied within this range for very small effect.
254 */
255 private static final int SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20;
256
257 /**
258 * The threshold value for using squaring code to perform multiplication
259 * of a {@code BigInteger} instance by itself. If the number of ints in
260 * the number are larger than this value, {@code multiply(this)} will
261 * return {@code square()}.
262 */
263 private static final int MULTIPLY_SQUARE_THRESHOLD = 20;
264
265 // Constructors
266
267 /**
268 * Translates a byte array containing the two's-complement binary
269 * representation of a BigInteger into a BigInteger. The input array is
270 * assumed to be in <i>big-endian</i> byte-order: the most significant
271 * byte is in the zeroth element.
272 *
273 * @param val big-endian two's-complement binary representation of
274 * BigInteger.
275 * @throws NumberFormatException {@code val} is zero bytes long.
276 */
277 public BigInteger(byte[] val) {
278 if (val.length == 0)
279 throw new NumberFormatException("Zero length BigInteger");
280
281 if (val[0] < 0) {
282 mag = makePositive(val);
283 signum = -1;
284 } else {
285 mag = stripLeadingZeroBytes(val);
286 signum = (mag.length == 0 ? 0 : 1);
287 }
288 if (mag.length >= MAX_MAG_LENGTH) {
289 checkRange();
290 }
291 }
292
293 /**
294 * This private constructor translates an int array containing the
295 * two's-complement binary representation of a BigInteger into a
296 * BigInteger. The input array is assumed to be in <i>big-endian</i>
297 * int-order: the most significant int is in the zeroth element.
298 */
299 private BigInteger(int[] val) {
300 if (val.length == 0)
301 throw new NumberFormatException("Zero length BigInteger");
302
303 if (val[0] < 0) {
304 mag = makePositive(val);
305 signum = -1;
306 } else {
307 mag = trustedStripLeadingZeroInts(val);
308 signum = (mag.length == 0 ? 0 : 1);
309 }
310 if (mag.length >= MAX_MAG_LENGTH) {
311 checkRange();
312 }
313 }
314
315 /**
316 * Translates the sign-magnitude representation of a BigInteger into a
317 * BigInteger. The sign is represented as an integer signum value: -1 for
318 * negative, 0 for zero, or 1 for positive. The magnitude is a byte array
319 * in <i>big-endian</i> byte-order: the most significant byte is in the
320 * zeroth element. A zero-length magnitude array is permissible, and will
321 * result in a BigInteger value of 0, whether signum is -1, 0 or 1.
322 *
323 * @param signum signum of the number (-1 for negative, 0 for zero, 1
324 * for positive).
325 * @param magnitude big-endian binary representation of the magnitude of
326 * the number.
327 * @throws NumberFormatException {@code signum} is not one of the three
328 * legal values (-1, 0, and 1), or {@code signum} is 0 and
329 * {@code magnitude} contains one or more non-zero bytes.
330 */
331 public BigInteger(int signum, byte[] magnitude) {
332 this.mag = stripLeadingZeroBytes(magnitude);
333
334 if (signum < -1 || signum > 1)
335 throw(new NumberFormatException("Invalid signum value"));
336
337 if (this.mag.length == 0) {
338 this.signum = 0;
339 } else {
340 if (signum == 0)
341 throw(new NumberFormatException("signum-magnitude mismatch"));
342 this.signum = signum;
343 }
344 if (mag.length >= MAX_MAG_LENGTH) {
345 checkRange();
346 }
347 }
348
349 /**
350 * A constructor for internal use that translates the sign-magnitude
351 * representation of a BigInteger into a BigInteger. It checks the
352 * arguments and copies the magnitude so this constructor would be
353 * safe for external use.
354 */
355 private BigInteger(int signum, int[] magnitude) {
356 this.mag = stripLeadingZeroInts(magnitude);
357
358 if (signum < -1 || signum > 1)
359 throw(new NumberFormatException("Invalid signum value"));
360
361 if (this.mag.length == 0) {
362 this.signum = 0;
363 } else {
364 if (signum == 0)
365 throw(new NumberFormatException("signum-magnitude mismatch"));
366 this.signum = signum;
367 }
368 if (mag.length >= MAX_MAG_LENGTH) {
369 checkRange();
1022
1023 /**
1024 * This internal constructor differs from its public cousin
1025 * with the arguments reversed in two ways: it assumes that its
1026 * arguments are correct, and it doesn't copy the magnitude array.
1027 */
1028 BigInteger(int[] magnitude, int signum) {
1029 this.signum = (magnitude.length == 0 ? 0 : signum);
1030 this.mag = magnitude;
1031 if (mag.length >= MAX_MAG_LENGTH) {
1032 checkRange();
1033 }
1034 }
1035
1036 /**
1037 * This private constructor is for internal use and assumes that its
1038 * arguments are correct.
1039 */
1040 private BigInteger(byte[] magnitude, int signum) {
1041 this.signum = (magnitude.length == 0 ? 0 : signum);
1042 this.mag = stripLeadingZeroBytes(magnitude);
1043 if (mag.length >= MAX_MAG_LENGTH) {
1044 checkRange();
1045 }
1046 }
1047
1048 /**
1049 * Throws an {@code ArithmeticException} if the {@code BigInteger} would be
1050 * out of the supported range.
1051 *
1052 * @throws ArithmeticException if {@code this} exceeds the supported range.
1053 */
1054 private void checkRange() {
1055 if (mag.length > MAX_MAG_LENGTH || mag.length == MAX_MAG_LENGTH && mag[0] < 0) {
1056 reportOverflow();
1057 }
1058 }
1059
1060 private static void reportOverflow() {
1061 throw new ArithmeticException("BigInteger would overflow supported range");
1062 }
3960 return java.util.Arrays.copyOfRange(val, keep, vlen);
3961 }
3962
3963 /**
3964 * Returns the input array stripped of any leading zero bytes.
3965 * Since the source is trusted the copying may be skipped.
3966 */
3967 private static int[] trustedStripLeadingZeroInts(int val[]) {
3968 int vlen = val.length;
3969 int keep;
3970
3971 // Find first nonzero byte
3972 for (keep = 0; keep < vlen && val[keep] == 0; keep++)
3973 ;
3974 return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen);
3975 }
3976
3977 /**
3978 * Returns a copy of the input array stripped of any leading zero bytes.
3979 */
3980 private static int[] stripLeadingZeroBytes(byte a[]) {
3981 int byteLength = a.length;
3982 int keep;
3983
3984 // Find first nonzero byte
3985 for (keep = 0; keep < byteLength && a[keep] == 0; keep++)
3986 ;
3987
3988 // Allocate new array and copy relevant part of input array
3989 int intLength = ((byteLength - keep) + 3) >>> 2;
3990 int[] result = new int[intLength];
3991 int b = byteLength - 1;
3992 for (int i = intLength-1; i >= 0; i--) {
3993 result[i] = a[b--] & 0xff;
3994 int bytesRemaining = b - keep + 1;
3995 int bytesToTransfer = Math.min(3, bytesRemaining);
3996 for (int j=8; j <= (bytesToTransfer << 3); j += 8)
3997 result[i] |= ((a[b--] & 0xff) << j);
3998 }
3999 return result;
4000 }
4001
4002 /**
4003 * Takes an array a representing a negative 2's-complement number and
4004 * returns the minimal (no leading zero bytes) unsigned whose value is -a.
4005 */
4006 private static int[] makePositive(byte a[]) {
4007 int keep, k;
4008 int byteLength = a.length;
4009
4010 // Find first non-sign (0xff) byte of input
4011 for (keep=0; keep < byteLength && a[keep] == -1; keep++)
4012 ;
4013
4014
4015 /* Allocate output array. If all non-sign bytes are 0x00, we must
4016 * allocate space for one extra output byte. */
4017 for (k=keep; k < byteLength && a[k] == 0; k++)
4018 ;
4019
4020 int extraByte = (k == byteLength) ? 1 : 0;
4021 int intLength = ((byteLength - keep + extraByte) + 3) >>> 2;
4022 int result[] = new int[intLength];
4023
4024 /* Copy one's complement of input into output, leaving extra
4025 * byte (if it exists) == 0x00 */
4026 int b = byteLength - 1;
4027 for (int i = intLength-1; i >= 0; i--) {
4028 result[i] = a[b--] & 0xff;
4029 int numBytesToTransfer = Math.min(3, b-keep+1);
4030 if (numBytesToTransfer < 0)
4031 numBytesToTransfer = 0;
4032 for (int j=8; j <= 8*numBytesToTransfer; j += 8)
4033 result[i] |= ((a[b--] & 0xff) << j);
4034
4035 // Mask indicates which bits must be complemented
4036 int mask = -1 >>> (8*(3-numBytesToTransfer));
4037 result[i] = ~result[i] & mask;
4038 }
4039
4040 // Add one to one's complement to generate two's complement
4041 for (int i=result.length-1; i >= 0; i--) {
4042 result[i] = (int)((result[i] & LONG_MASK) + 1);
4043 if (result[i] != 0)
4044 break;
4045 }
4046
4231 * marker value. Therefore, no explicit action to set these fields needs to
4232 * be taken in readObject because those fields already have a 0 value by
4233 * default since defaultReadObject is not being used.
4234 */
4235 private void readObject(java.io.ObjectInputStream s)
4236 throws java.io.IOException, ClassNotFoundException {
4237 // prepare to read the alternate persistent fields
4238 ObjectInputStream.GetField fields = s.readFields();
4239
4240 // Read the alternate persistent fields that we care about
4241 int sign = fields.get("signum", -2);
4242 byte[] magnitude = (byte[])fields.get("magnitude", null);
4243
4244 // Validate signum
4245 if (sign < -1 || sign > 1) {
4246 String message = "BigInteger: Invalid signum value";
4247 if (fields.defaulted("signum"))
4248 message = "BigInteger: Signum not present in stream";
4249 throw new java.io.StreamCorruptedException(message);
4250 }
4251 int[] mag = stripLeadingZeroBytes(magnitude);
4252 if ((mag.length == 0) != (sign == 0)) {
4253 String message = "BigInteger: signum-magnitude mismatch";
4254 if (fields.defaulted("magnitude"))
4255 message = "BigInteger: Magnitude not present in stream";
4256 throw new java.io.StreamCorruptedException(message);
4257 }
4258
4259 // Commit final fields via Unsafe
4260 UnsafeHolder.putSign(this, sign);
4261
4262 // Calculate mag field from magnitude and discard magnitude
4263 UnsafeHolder.putMag(this, mag);
4264 if (mag.length >= MAX_MAG_LENGTH) {
4265 try {
4266 checkRange();
4267 } catch (ArithmeticException e) {
4268 throw new java.io.StreamCorruptedException("BigInteger: Out of the supported range");
4269 }
4270 }
4271 }
|
248 * The threshold value for using Schoenhage recursive base conversion. If
249 * the number of ints in the number are larger than this value,
250 * the Schoenhage algorithm will be used. In practice, it appears that the
251 * Schoenhage routine is faster for any threshold down to 2, and is
252 * relatively flat for thresholds between 2-25, so this choice may be
253 * varied within this range for very small effect.
254 */
255 private static final int SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20;
256
257 /**
258 * The threshold value for using squaring code to perform multiplication
259 * of a {@code BigInteger} instance by itself. If the number of ints in
260 * the number are larger than this value, {@code multiply(this)} will
261 * return {@code square()}.
262 */
263 private static final int MULTIPLY_SQUARE_THRESHOLD = 20;
264
265 // Constructors
266
267 /**
268 * Translates a byte sub-array containing the two's-complement binary
269 * representation of a BigInteger into a BigInteger. The sub-array is
270 * specified via an offset into the array and a length. The sub-array is
271 * assumed to be in <i>big-endian</i> byte-order: the most significant
272 * byte is the element at index {@code off}.
273 *
274 * An {@code IndexOutOfBoundsException} is thrown if the length of the array
275 * {@code val} is non-zero and either {@code off} is negative, {@code len}
276 * is negative, or {@code off+len} is greater than the length of
277 * {@code val}.
278 *
279 * @param val byte array containing a sub-array which is the big-endian
280 * two's-complement binary representation of a BigInteger.
281 * @param off the start offset of the binary representation.
282 * @param len the number of bytes to use.
283 * @throws NumberFormatException {@code val} is zero bytes long.
284 */
285 public BigInteger(byte[] val, int off, int len) {
286 if (val.length == 0) {
287 throw new NumberFormatException("Zero length BigInteger");
288 } else if ((off < 0) || (off > val.length) || (len < 0) ||
289 ((off + len) > val.length) || ((off + len) < 0)) {
290 throw new IndexOutOfBoundsException();
291 }
292
293 if (val[off] < 0) {
294 mag = makePositive(val, off, len);
295 signum = -1;
296 } else {
297 mag = stripLeadingZeroBytes(val, off, len);
298 signum = (mag.length == 0 ? 0 : 1);
299 }
300 if (mag.length >= MAX_MAG_LENGTH) {
301 checkRange();
302 }
303 }
304
305 /**
306 * Translates a byte array containing the two's-complement binary
307 * representation of a BigInteger into a BigInteger. The input array is
308 * assumed to be in <i>big-endian</i> byte-order: the most significant
309 * byte is in the zeroth element.
310 *
311 * @param val big-endian two's-complement binary representation of a
312 * BigInteger.
313 * @throws NumberFormatException {@code val} is zero bytes long.
314 */
315 public BigInteger(byte[] val) {
316 this(val, 0, val.length);
317 }
318
319 /**
320 * This private constructor translates an int array containing the
321 * two's-complement binary representation of a BigInteger into a
322 * BigInteger. The input array is assumed to be in <i>big-endian</i>
323 * int-order: the most significant int is in the zeroth element.
324 */
325 private BigInteger(int[] val) {
326 if (val.length == 0)
327 throw new NumberFormatException("Zero length BigInteger");
328
329 if (val[0] < 0) {
330 mag = makePositive(val);
331 signum = -1;
332 } else {
333 mag = trustedStripLeadingZeroInts(val);
334 signum = (mag.length == 0 ? 0 : 1);
335 }
336 if (mag.length >= MAX_MAG_LENGTH) {
337 checkRange();
338 }
339 }
340
341 /**
342 * Translates the sign-magnitude representation of a BigInteger into a
343 * BigInteger. The sign is represented as an integer signum value: -1 for
344 * negative, 0 for zero, or 1 for positive. The magnitude is a sub-array of
345 * a byte array in <i>big-endian</i> byte-order: the most significant byte
346 * is the element at index {@code off}. A zero value of the length
347 * {@code len} is permissible, and will result in a BigInteger value of 0,
348 * whether signum is -1, 0 or 1.
349 *
350 * An {@code IndexOutOfBoundsException} is thrown if the length of the array
351 * {@code magnitude} is non-zero and either {@code off} is negative,
352 * {@code len} is negative, or {@code off+len} is greater than the length of
353 * {@code magnitude}.
354 *
355 * @param signum signum of the number (-1 for negative, 0 for zero, 1
356 * for positive).
357 * @param magnitude big-endian binary representation of the magnitude of
358 * the number.
359 * @throws NumberFormatException {@code signum} is not one of the three
360 * legal values (-1, 0, and 1), or {@code signum} is 0 and
361 * {@code magnitude} contains one or more non-zero bytes.
362 */
363 public BigInteger(int signum, byte[] magnitude, int off, int len) {
364 if ((off < 0) || (off > magnitude.length) || (len < 0)
365 || ((off + len) > magnitude.length) || ((off + len) < 0)) {
366 throw new IndexOutOfBoundsException();
367 }
368 this.mag = stripLeadingZeroBytes(magnitude, off, len);
369
370 if (signum < -1 || signum > 1)
371 throw(new NumberFormatException("Invalid signum value"));
372
373 if (this.mag.length == 0) {
374 this.signum = 0;
375 } else {
376 if (signum == 0)
377 throw(new NumberFormatException("signum-magnitude mismatch"));
378 this.signum = signum;
379 }
380 if (mag.length >= MAX_MAG_LENGTH) {
381 checkRange();
382 }
383 }
384
385 /**
386 * Translates the sign-magnitude representation of a BigInteger into a
387 * BigInteger. The sign is represented as an integer signum value: -1 for
388 * negative, 0 for zero, or 1 for positive. The magnitude is a byte array
389 * in <i>big-endian</i> byte-order: the most significant byte is the
390 * zeroth element. A zero-length magnitude array is permissible, and will
391 * result in a BigInteger value of 0, whether signum is -1, 0 or 1.
392 *
393 * @param signum signum of the number (-1 for negative, 0 for zero, 1
394 * for positive).
395 * @param magnitude big-endian binary representation of the magnitude of
396 * the number.
397 * @throws NumberFormatException {@code signum} is not one of the three
398 * legal values (-1, 0, and 1), or {@code signum} is 0 and
399 * {@code magnitude} contains one or more non-zero bytes.
400 */
401 public BigInteger(int signum, byte[] magnitude) {
402 this(signum, magnitude, 0, magnitude.length);
403 }
404
405 /**
406 * A constructor for internal use that translates the sign-magnitude
407 * representation of a BigInteger into a BigInteger. It checks the
408 * arguments and copies the magnitude so this constructor would be
409 * safe for external use.
410 */
411 private BigInteger(int signum, int[] magnitude) {
412 this.mag = stripLeadingZeroInts(magnitude);
413
414 if (signum < -1 || signum > 1)
415 throw(new NumberFormatException("Invalid signum value"));
416
417 if (this.mag.length == 0) {
418 this.signum = 0;
419 } else {
420 if (signum == 0)
421 throw(new NumberFormatException("signum-magnitude mismatch"));
422 this.signum = signum;
423 }
424 if (mag.length >= MAX_MAG_LENGTH) {
425 checkRange();
1078
1079 /**
1080 * This internal constructor differs from its public cousin
1081 * with the arguments reversed in two ways: it assumes that its
1082 * arguments are correct, and it doesn't copy the magnitude array.
1083 */
1084 BigInteger(int[] magnitude, int signum) {
1085 this.signum = (magnitude.length == 0 ? 0 : signum);
1086 this.mag = magnitude;
1087 if (mag.length >= MAX_MAG_LENGTH) {
1088 checkRange();
1089 }
1090 }
1091
1092 /**
1093 * This private constructor is for internal use and assumes that its
1094 * arguments are correct.
1095 */
1096 private BigInteger(byte[] magnitude, int signum) {
1097 this.signum = (magnitude.length == 0 ? 0 : signum);
1098 this.mag = stripLeadingZeroBytes(magnitude, 0, magnitude.length);
1099 if (mag.length >= MAX_MAG_LENGTH) {
1100 checkRange();
1101 }
1102 }
1103
1104 /**
1105 * Throws an {@code ArithmeticException} if the {@code BigInteger} would be
1106 * out of the supported range.
1107 *
1108 * @throws ArithmeticException if {@code this} exceeds the supported range.
1109 */
1110 private void checkRange() {
1111 if (mag.length > MAX_MAG_LENGTH || mag.length == MAX_MAG_LENGTH && mag[0] < 0) {
1112 reportOverflow();
1113 }
1114 }
1115
1116 private static void reportOverflow() {
1117 throw new ArithmeticException("BigInteger would overflow supported range");
1118 }
4016 return java.util.Arrays.copyOfRange(val, keep, vlen);
4017 }
4018
4019 /**
4020 * Returns the input array stripped of any leading zero bytes.
4021 * Since the source is trusted the copying may be skipped.
4022 */
4023 private static int[] trustedStripLeadingZeroInts(int val[]) {
4024 int vlen = val.length;
4025 int keep;
4026
4027 // Find first nonzero byte
4028 for (keep = 0; keep < vlen && val[keep] == 0; keep++)
4029 ;
4030 return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen);
4031 }
4032
4033 /**
4034 * Returns a copy of the input array stripped of any leading zero bytes.
4035 */
4036 private static int[] stripLeadingZeroBytes(byte a[], int off, int len) {
4037 int indexBound = off + len;
4038 int keep;
4039
4040 // Find first nonzero byte
4041 for (keep = off; keep < indexBound && a[keep] == 0; keep++)
4042 ;
4043
4044 // Allocate new array and copy relevant part of input array
4045 int intLength = ((indexBound - keep) + 3) >>> 2;
4046 int[] result = new int[intLength];
4047 int b = indexBound - 1;
4048 for (int i = intLength-1; i >= 0; i--) {
4049 result[i] = a[b--] & 0xff;
4050 int bytesRemaining = b - keep + 1;
4051 int bytesToTransfer = Math.min(3, bytesRemaining);
4052 for (int j=8; j <= (bytesToTransfer << 3); j += 8)
4053 result[i] |= ((a[b--] & 0xff) << j);
4054 }
4055 return result;
4056 }
4057
4058 /**
4059 * Takes an array a representing a negative 2's-complement number and
4060 * returns the minimal (no leading zero bytes) unsigned whose value is -a.
4061 */
4062 private static int[] makePositive(byte a[], int off, int len) {
4063 int keep, k;
4064 int indexBound = off + len;
4065
4066 // Find first non-sign (0xff) byte of input
4067 for (keep=off; keep < indexBound && a[keep] == -1; keep++)
4068 ;
4069
4070
4071 /* Allocate output array. If all non-sign bytes are 0x00, we must
4072 * allocate space for one extra output byte. */
4073 for (k=keep; k < indexBound && a[k] == 0; k++)
4074 ;
4075
4076 int extraByte = (k == indexBound) ? 1 : 0;
4077 int intLength = ((indexBound - keep + extraByte) + 3) >>> 2;
4078 int result[] = new int[intLength];
4079
4080 /* Copy one's complement of input into output, leaving extra
4081 * byte (if it exists) == 0x00 */
4082 int b = indexBound - 1;
4083 for (int i = intLength-1; i >= 0; i--) {
4084 result[i] = a[b--] & 0xff;
4085 int numBytesToTransfer = Math.min(3, b-keep+1);
4086 if (numBytesToTransfer < 0)
4087 numBytesToTransfer = 0;
4088 for (int j=8; j <= 8*numBytesToTransfer; j += 8)
4089 result[i] |= ((a[b--] & 0xff) << j);
4090
4091 // Mask indicates which bits must be complemented
4092 int mask = -1 >>> (8*(3-numBytesToTransfer));
4093 result[i] = ~result[i] & mask;
4094 }
4095
4096 // Add one to one's complement to generate two's complement
4097 for (int i=result.length-1; i >= 0; i--) {
4098 result[i] = (int)((result[i] & LONG_MASK) + 1);
4099 if (result[i] != 0)
4100 break;
4101 }
4102
4287 * marker value. Therefore, no explicit action to set these fields needs to
4288 * be taken in readObject because those fields already have a 0 value by
4289 * default since defaultReadObject is not being used.
4290 */
4291 private void readObject(java.io.ObjectInputStream s)
4292 throws java.io.IOException, ClassNotFoundException {
4293 // prepare to read the alternate persistent fields
4294 ObjectInputStream.GetField fields = s.readFields();
4295
4296 // Read the alternate persistent fields that we care about
4297 int sign = fields.get("signum", -2);
4298 byte[] magnitude = (byte[])fields.get("magnitude", null);
4299
4300 // Validate signum
4301 if (sign < -1 || sign > 1) {
4302 String message = "BigInteger: Invalid signum value";
4303 if (fields.defaulted("signum"))
4304 message = "BigInteger: Signum not present in stream";
4305 throw new java.io.StreamCorruptedException(message);
4306 }
4307 int[] mag = stripLeadingZeroBytes(magnitude, 0, magnitude.length);
4308 if ((mag.length == 0) != (sign == 0)) {
4309 String message = "BigInteger: signum-magnitude mismatch";
4310 if (fields.defaulted("magnitude"))
4311 message = "BigInteger: Magnitude not present in stream";
4312 throw new java.io.StreamCorruptedException(message);
4313 }
4314
4315 // Commit final fields via Unsafe
4316 UnsafeHolder.putSign(this, sign);
4317
4318 // Calculate mag field from magnitude and discard magnitude
4319 UnsafeHolder.putMag(this, mag);
4320 if (mag.length >= MAX_MAG_LENGTH) {
4321 try {
4322 checkRange();
4323 } catch (ArithmeticException e) {
4324 throw new java.io.StreamCorruptedException("BigInteger: Out of the supported range");
4325 }
4326 }
4327 }
|