1 /* 2 * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 // This file is available under and governed by the GNU General Public 27 // License version 2 only, as published by the Free Software Foundation. 28 // However, the following notice accompanied the original version of this 29 // file: 30 // 31 // Copyright 2010 the V8 project authors. All rights reserved. 32 // Redistribution and use in source and binary forms, with or without 33 // modification, are permitted provided that the following conditions are 34 // met: 35 // 36 // * Redistributions of source code must retain the above copyright 37 // notice, this list of conditions and the following disclaimer. 38 // * Redistributions in binary form must reproduce the above 39 // copyright notice, this list of conditions and the following 40 // disclaimer in the documentation and/or other materials provided 41 // with the distribution. 42 // * Neither the name of Google Inc. nor the names of its 43 // contributors may be used to endorse or promote products derived 44 // from this software without specific prior written permission. 45 // 46 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 47 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 48 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 49 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 50 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 51 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 52 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 53 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 54 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 55 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 56 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 57 58 package jdk.nashorn.internal.runtime.doubleconv; 59 60 import java.util.Arrays; 61 62 class Bignum { 63 64 // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately. 65 // This bignum can encode much bigger numbers, since it contains an 66 // exponent. 67 static final int kMaxSignificantBits = 3584; 68 69 static final int kChunkSize = 32; // size of int 70 static final int kDoubleChunkSize = 64; // size of long 71 // With bigit size of 28 we loose some bits, but a double still fits easily 72 // into two ints, and more importantly we can use the Comba multiplication. 73 static final int kBigitSize = 28; 74 static final int kBigitMask = (1 << kBigitSize) - 1; 75 // Every instance allocates kbigitLength ints on the stack. Bignums cannot 76 // grow. There are no checks if the stack-allocated space is sufficient. 77 static final int kBigitCapacity = kMaxSignificantBits / kBigitSize; 78 79 private int[] bigits_ = new int[kBigitCapacity]; 80 // A vector backed by bigits_buffer_. This way accesses to the array are 81 // checked for out-of-bounds errors. 82 // Vector<int> bigits_; 83 private int used_digits_; 84 // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize). 85 private int exponent_; 86 87 Bignum() {} 88 89 void times10() { multiplyByUInt32(10); } 90 91 static boolean equal(final Bignum a, final Bignum b) { 92 return compare(a, b) == 0; 93 } 94 static boolean lessEqual(final Bignum a, final Bignum b) { 95 return compare(a, b) <= 0; 96 } 97 static boolean less(final Bignum a, final Bignum b) { 98 return compare(a, b) < 0; 99 } 100 101 // Returns a + b == c 102 static boolean plusEqual(final Bignum a, final Bignum b, final Bignum c) { 103 return plusCompare(a, b, c) == 0; 104 } 105 // Returns a + b <= c 106 static boolean plusLessEqual(final Bignum a, final Bignum b, final Bignum c) { 107 return plusCompare(a, b, c) <= 0; 108 } 109 // Returns a + b < c 110 static boolean plusLess(final Bignum a, final Bignum b, final Bignum c) { 111 return plusCompare(a, b, c) < 0; 112 } 113 114 private void ensureCapacity(final int size) { 115 if (size > kBigitCapacity) { 116 throw new RuntimeException(); 117 } 118 } 119 120 // BigitLength includes the "hidden" digits encoded in the exponent. 121 int bigitLength() { return used_digits_ + exponent_; } 122 123 // Guaranteed to lie in one Bigit. 124 void assignUInt16(final char value) { 125 assert (kBigitSize >= 16); 126 zero(); 127 if (value == 0) return; 128 129 ensureCapacity(1); 130 bigits_[0] = value; 131 used_digits_ = 1; 132 } 133 134 135 void assignUInt64(long value) { 136 final int kUInt64Size = 64; 137 138 zero(); 139 if (value == 0) return; 140 141 final int needed_bigits = kUInt64Size / kBigitSize + 1; 142 ensureCapacity(needed_bigits); 143 for (int i = 0; i < needed_bigits; ++i) { 144 bigits_[i] = (int) (value & kBigitMask); 145 value = value >>> kBigitSize; 146 } 147 used_digits_ = needed_bigits; 148 clamp(); 149 } 150 151 152 void assignBignum(final Bignum other) { 153 exponent_ = other.exponent_; 154 for (int i = 0; i < other.used_digits_; ++i) { 155 bigits_[i] = other.bigits_[i]; 156 } 157 // Clear the excess digits (if there were any). 158 for (int i = other.used_digits_; i < used_digits_; ++i) { 159 bigits_[i] = 0; 160 } 161 used_digits_ = other.used_digits_; 162 } 163 164 165 static long readUInt64(final String str, 166 final int from, 167 final int digits_to_read) { 168 long result = 0; 169 for (int i = from; i < from + digits_to_read; ++i) { 170 final int digit = str.charAt(i) - '0'; 171 assert (0 <= digit && digit <= 9); 172 result = result * 10 + digit; 173 } 174 return result; 175 } 176 177 178 void assignDecimalString(final String str) { 179 // 2^64 = 18446744073709551616 > 10^19 180 final int kMaxUint64DecimalDigits = 19; 181 zero(); 182 int length = str.length(); 183 int pos = 0; 184 // Let's just say that each digit needs 4 bits. 185 while (length >= kMaxUint64DecimalDigits) { 186 final long digits = readUInt64(str, pos, kMaxUint64DecimalDigits); 187 pos += kMaxUint64DecimalDigits; 188 length -= kMaxUint64DecimalDigits; 189 multiplyByPowerOfTen(kMaxUint64DecimalDigits); 190 addUInt64(digits); 191 } 192 final long digits = readUInt64(str, pos, length); 193 multiplyByPowerOfTen(length); 194 addUInt64(digits); 195 clamp(); 196 } 197 198 199 static int hexCharValue(final char c) { 200 if ('0' <= c && c <= '9') return c - '0'; 201 if ('a' <= c && c <= 'f') return 10 + c - 'a'; 202 assert ('A' <= c && c <= 'F'); 203 return 10 + c - 'A'; 204 } 205 206 207 void assignHexString(final String str) { 208 zero(); 209 final int length = str.length(); 210 211 final int needed_bigits = length * 4 / kBigitSize + 1; 212 ensureCapacity(needed_bigits); 213 int string_index = length - 1; 214 for (int i = 0; i < needed_bigits - 1; ++i) { 215 // These bigits are guaranteed to be "full". 216 int current_bigit = 0; 217 for (int j = 0; j < kBigitSize / 4; j++) { 218 current_bigit += hexCharValue(str.charAt(string_index--)) << (j * 4); 219 } 220 bigits_[i] = current_bigit; 221 } 222 used_digits_ = needed_bigits - 1; 223 224 int most_significant_bigit = 0; // Could be = 0; 225 for (int j = 0; j <= string_index; ++j) { 226 most_significant_bigit <<= 4; 227 most_significant_bigit += hexCharValue(str.charAt(j)); 228 } 229 if (most_significant_bigit != 0) { 230 bigits_[used_digits_] = most_significant_bigit; 231 used_digits_++; 232 } 233 clamp(); 234 } 235 236 237 void addUInt64(final long operand) { 238 if (operand == 0) return; 239 final Bignum other = new Bignum(); 240 other.assignUInt64(operand); 241 addBignum(other); 242 } 243 244 245 void addBignum(final Bignum other) { 246 assert (isClamped()); 247 assert (other.isClamped()); 248 249 // If this has a greater exponent than other append zero-bigits to this. 250 // After this call exponent_ <= other.exponent_. 251 align(other); 252 253 // There are two possibilities: 254 // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) 255 // bbbbb 00000000 256 // ---------------- 257 // ccccccccccc 0000 258 // or 259 // aaaaaaaaaa 0000 260 // bbbbbbbbb 0000000 261 // ----------------- 262 // cccccccccccc 0000 263 // In both cases we might need a carry bigit. 264 265 ensureCapacity(1 + Math.max(bigitLength(), other.bigitLength()) - exponent_); 266 int carry = 0; 267 int bigit_pos = other.exponent_ - exponent_; 268 assert (bigit_pos >= 0); 269 for (int i = 0; i < other.used_digits_; ++i) { 270 final int sum = bigits_[bigit_pos] + other.bigits_[i] + carry; 271 bigits_[bigit_pos] = sum & kBigitMask; 272 carry = sum >>> kBigitSize; 273 bigit_pos++; 274 } 275 276 while (carry != 0) { 277 final int sum = bigits_[bigit_pos] + carry; 278 bigits_[bigit_pos] = sum & kBigitMask; 279 carry = sum >>> kBigitSize; 280 bigit_pos++; 281 } 282 used_digits_ = Math.max(bigit_pos, used_digits_); 283 assert (isClamped()); 284 } 285 286 287 void subtractBignum(final Bignum other) { 288 assert (isClamped()); 289 assert (other.isClamped()); 290 // We require this to be bigger than other. 291 assert (lessEqual(other, this)); 292 293 align(other); 294 295 final int offset = other.exponent_ - exponent_; 296 int borrow = 0; 297 int i; 298 for (i = 0; i < other.used_digits_; ++i) { 299 assert ((borrow == 0) || (borrow == 1)); 300 final int difference = bigits_[i + offset] - other.bigits_[i] - borrow; 301 bigits_[i + offset] = difference & kBigitMask; 302 borrow = difference >>> (kChunkSize - 1); 303 } 304 while (borrow != 0) { 305 final int difference = bigits_[i + offset] - borrow; 306 bigits_[i + offset] = difference & kBigitMask; 307 borrow = difference >>> (kChunkSize - 1); 308 ++i; 309 } 310 clamp(); 311 } 312 313 314 void shiftLeft(final int shift_amount) { 315 if (used_digits_ == 0) return; 316 exponent_ += shift_amount / kBigitSize; 317 final int local_shift = shift_amount % kBigitSize; 318 ensureCapacity(used_digits_ + 1); 319 bigitsShiftLeft(local_shift); 320 } 321 322 323 void multiplyByUInt32(final int factor) { 324 if (factor == 1) return; 325 if (factor == 0) { 326 zero(); 327 return; 328 } 329 if (used_digits_ == 0) return; 330 331 // The product of a bigit with the factor is of size kBigitSize + 32. 332 // Assert that this number + 1 (for the carry) fits into double int. 333 assert (kDoubleChunkSize >= kBigitSize + 32 + 1); 334 long carry = 0; 335 for (int i = 0; i < used_digits_; ++i) { 336 final long product = (factor & 0xFFFFFFFFL) * bigits_[i] + carry; 337 bigits_[i] = (int) (product & kBigitMask); 338 carry = product >>> kBigitSize; 339 } 340 while (carry != 0) { 341 ensureCapacity(used_digits_ + 1); 342 bigits_[used_digits_] = (int) (carry & kBigitMask); 343 used_digits_++; 344 carry >>>= kBigitSize; 345 } 346 } 347 348 349 void multiplyByUInt64(final long factor) { 350 if (factor == 1) return; 351 if (factor == 0) { 352 zero(); 353 return; 354 } 355 assert (kBigitSize < 32); 356 long carry = 0; 357 final long low = factor & 0xFFFFFFFFL; 358 final long high = factor >>> 32; 359 for (int i = 0; i < used_digits_; ++i) { 360 final long product_low = low * bigits_[i]; 361 final long product_high = high * bigits_[i]; 362 final long tmp = (carry & kBigitMask) + product_low; 363 bigits_[i] = (int) (tmp & kBigitMask); 364 carry = (carry >>> kBigitSize) + (tmp >>> kBigitSize) + 365 (product_high << (32 - kBigitSize)); 366 } 367 while (carry != 0) { 368 ensureCapacity(used_digits_ + 1); 369 bigits_[used_digits_] = (int) (carry & kBigitMask); 370 used_digits_++; 371 carry >>>= kBigitSize; 372 } 373 } 374 375 376 void multiplyByPowerOfTen(final int exponent) { 377 final long kFive27 = 0x6765c793fa10079dL; 378 final int kFive1 = 5; 379 final int kFive2 = kFive1 * 5; 380 final int kFive3 = kFive2 * 5; 381 final int kFive4 = kFive3 * 5; 382 final int kFive5 = kFive4 * 5; 383 final int kFive6 = kFive5 * 5; 384 final int kFive7 = kFive6 * 5; 385 final int kFive8 = kFive7 * 5; 386 final int kFive9 = kFive8 * 5; 387 final int kFive10 = kFive9 * 5; 388 final int kFive11 = kFive10 * 5; 389 final int kFive12 = kFive11 * 5; 390 final int kFive13 = kFive12 * 5; 391 final int kFive1_to_12[] = 392 { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, 393 kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; 394 395 assert (exponent >= 0); 396 if (exponent == 0) return; 397 if (used_digits_ == 0) return; 398 399 // We shift by exponent at the end just before returning. 400 int remaining_exponent = exponent; 401 while (remaining_exponent >= 27) { 402 multiplyByUInt64(kFive27); 403 remaining_exponent -= 27; 404 } 405 while (remaining_exponent >= 13) { 406 multiplyByUInt32(kFive13); 407 remaining_exponent -= 13; 408 } 409 if (remaining_exponent > 0) { 410 multiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); 411 } 412 shiftLeft(exponent); 413 } 414 415 416 void square() { 417 assert (isClamped()); 418 final int product_length = 2 * used_digits_; 419 ensureCapacity(product_length); 420 421 // Comba multiplication: compute each column separately. 422 // Example: r = a2a1a0 * b2b1b0. 423 // r = 1 * a0b0 + 424 // 10 * (a1b0 + a0b1) + 425 // 100 * (a2b0 + a1b1 + a0b2) + 426 // 1000 * (a2b1 + a1b2) + 427 // 10000 * a2b2 428 // 429 // In the worst case we have to accumulate nb-digits products of digit*digit. 430 // 431 // Assert that the additional number of bits in a DoubleChunk are enough to 432 // sum up used_digits of Bigit*Bigit. 433 if ((1L << (2 * (kChunkSize - kBigitSize))) <= used_digits_) { 434 throw new RuntimeException("unimplemented"); 435 } 436 long accumulator = 0; 437 // First shift the digits so we don't overwrite them. 438 final int copy_offset = used_digits_; 439 for (int i = 0; i < used_digits_; ++i) { 440 bigits_[copy_offset + i] = bigits_[i]; 441 } 442 // We have two loops to avoid some 'if's in the loop. 443 for (int i = 0; i < used_digits_; ++i) { 444 // Process temporary digit i with power i. 445 // The sum of the two indices must be equal to i. 446 int bigit_index1 = i; 447 int bigit_index2 = 0; 448 // Sum all of the sub-products. 449 while (bigit_index1 >= 0) { 450 final int int1 = bigits_[copy_offset + bigit_index1]; 451 final int int2 = bigits_[copy_offset + bigit_index2]; 452 accumulator += ((long) int1) * int2; 453 bigit_index1--; 454 bigit_index2++; 455 } 456 bigits_[i] = (int) (accumulator & kBigitMask); 457 accumulator >>>= kBigitSize; 458 } 459 for (int i = used_digits_; i < product_length; ++i) { 460 int bigit_index1 = used_digits_ - 1; 461 int bigit_index2 = i - bigit_index1; 462 // Invariant: sum of both indices is again equal to i. 463 // Inner loop runs 0 times on last iteration, emptying accumulator. 464 while (bigit_index2 < used_digits_) { 465 final int int1 = bigits_[copy_offset + bigit_index1]; 466 final int int2 = bigits_[copy_offset + bigit_index2]; 467 accumulator += ((long) int1) * int2; 468 bigit_index1--; 469 bigit_index2++; 470 } 471 // The overwritten bigits_[i] will never be read in further loop iterations, 472 // because bigit_index1 and bigit_index2 are always greater 473 // than i - used_digits_. 474 bigits_[i] = (int) (accumulator & kBigitMask); 475 accumulator >>>= kBigitSize; 476 } 477 // Since the result was guaranteed to lie inside the number the 478 // accumulator must be 0 now. 479 assert (accumulator == 0); 480 481 // Don't forget to update the used_digits and the exponent. 482 used_digits_ = product_length; 483 exponent_ *= 2; 484 clamp(); 485 } 486 487 488 void assignPowerUInt16(int base, final int power_exponent) { 489 assert (base != 0); 490 assert (power_exponent >= 0); 491 if (power_exponent == 0) { 492 assignUInt16((char) 1); 493 return; 494 } 495 zero(); 496 int shifts = 0; 497 // We expect base to be in range 2-32, and most often to be 10. 498 // It does not make much sense to implement different algorithms for counting 499 // the bits. 500 while ((base & 1) == 0) { 501 base >>>= 1; 502 shifts++; 503 } 504 int bit_size = 0; 505 int tmp_base = base; 506 while (tmp_base != 0) { 507 tmp_base >>>= 1; 508 bit_size++; 509 } 510 final int final_size = bit_size * power_exponent; 511 // 1 extra bigit for the shifting, and one for rounded final_size. 512 ensureCapacity(final_size / kBigitSize + 2); 513 514 // Left to Right exponentiation. 515 int mask = 1; 516 while (power_exponent >= mask) mask <<= 1; 517 518 // The mask is now pointing to the bit above the most significant 1-bit of 519 // power_exponent. 520 // Get rid of first 1-bit; 521 mask >>>= 2; 522 long this_value = base; 523 524 boolean delayed_multipliciation = false; 525 final long max_32bits = 0xFFFFFFFFL; 526 while (mask != 0 && this_value <= max_32bits) { 527 this_value = this_value * this_value; 528 // Verify that there is enough space in this_value to perform the 529 // multiplication. The first bit_size bits must be 0. 530 if ((power_exponent & mask) != 0) { 531 final long base_bits_mask = 532 ~((1L << (64 - bit_size)) - 1); 533 final boolean high_bits_zero = (this_value & base_bits_mask) == 0; 534 if (high_bits_zero) { 535 this_value *= base; 536 } else { 537 delayed_multipliciation = true; 538 } 539 } 540 mask >>>= 1; 541 } 542 assignUInt64(this_value); 543 if (delayed_multipliciation) { 544 multiplyByUInt32(base); 545 } 546 547 // Now do the same thing as a bignum. 548 while (mask != 0) { 549 square(); 550 if ((power_exponent & mask) != 0) { 551 multiplyByUInt32(base); 552 } 553 mask >>>= 1; 554 } 555 556 // And finally add the saved shifts. 557 shiftLeft(shifts * power_exponent); 558 } 559 560 561 // Precondition: this/other < 16bit. 562 char divideModuloIntBignum(final Bignum other) { 563 assert (isClamped()); 564 assert (other.isClamped()); 565 assert (other.used_digits_ > 0); 566 567 // Easy case: if we have less digits than the divisor than the result is 0. 568 // Note: this handles the case where this == 0, too. 569 if (bigitLength() < other.bigitLength()) { 570 return 0; 571 } 572 573 align(other); 574 575 char result = 0; 576 577 // Start by removing multiples of 'other' until both numbers have the same 578 // number of digits. 579 while (bigitLength() > other.bigitLength()) { 580 // This naive approach is extremely inefficient if `this` divided by other 581 // is big. This function is implemented for doubleToString where 582 // the result should be small (less than 10). 583 assert (other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16)); 584 assert (bigits_[used_digits_ - 1] < 0x10000); 585 // Remove the multiples of the first digit. 586 // Example this = 23 and other equals 9. -> Remove 2 multiples. 587 result += (bigits_[used_digits_ - 1]); 588 subtractTimes(other, bigits_[used_digits_ - 1]); 589 } 590 591 assert (bigitLength() == other.bigitLength()); 592 593 // Both bignums are at the same length now. 594 // Since other has more than 0 digits we know that the access to 595 // bigits_[used_digits_ - 1] is safe. 596 final int this_bigit = bigits_[used_digits_ - 1]; 597 final int other_bigit = other.bigits_[other.used_digits_ - 1]; 598 599 if (other.used_digits_ == 1) { 600 // Shortcut for easy (and common) case. 601 final int quotient = Integer.divideUnsigned(this_bigit, other_bigit); 602 bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient; 603 assert (Integer.compareUnsigned(quotient, 0x10000) < 0); 604 result += quotient; 605 clamp(); 606 return result; 607 } 608 609 final int division_estimate = Integer.divideUnsigned(this_bigit, (other_bigit + 1)); 610 assert (Integer.compareUnsigned(division_estimate, 0x10000) < 0); 611 result += division_estimate; 612 subtractTimes(other, division_estimate); 613 614 if (other_bigit * (division_estimate + 1) > this_bigit) { 615 // No need to even try to subtract. Even if other's remaining digits were 0 616 // another subtraction would be too much. 617 return result; 618 } 619 620 while (lessEqual(other, this)) { 621 subtractBignum(other); 622 result++; 623 } 624 return result; 625 } 626 627 628 static int sizeInHexChars(int number) { 629 assert (number > 0); 630 int result = 0; 631 while (number != 0) { 632 number >>>= 4; 633 result++; 634 } 635 return result; 636 } 637 638 639 static char hexCharOfValue(final int value) { 640 assert (0 <= value && value <= 16); 641 if (value < 10) return (char) (value + '0'); 642 return (char) (value - 10 + 'A'); 643 } 644 645 646 String toHexString() { 647 assert (isClamped()); 648 // Each bigit must be printable as separate hex-character. 649 assert (kBigitSize % 4 == 0); 650 final int kHexCharsPerBigit = kBigitSize / 4; 651 652 if (used_digits_ == 0) { 653 return "0"; 654 } 655 656 final int needed_chars = (bigitLength() - 1) * kHexCharsPerBigit + 657 sizeInHexChars(bigits_[used_digits_ - 1]); 658 final StringBuilder buffer = new StringBuilder(needed_chars); 659 buffer.setLength(needed_chars); 660 661 int string_index = needed_chars - 1; 662 for (int i = 0; i < exponent_; ++i) { 663 for (int j = 0; j < kHexCharsPerBigit; ++j) { 664 buffer.setCharAt(string_index--, '0'); 665 } 666 } 667 for (int i = 0; i < used_digits_ - 1; ++i) { 668 int current_bigit = bigits_[i]; 669 for (int j = 0; j < kHexCharsPerBigit; ++j) { 670 buffer.setCharAt(string_index--, hexCharOfValue(current_bigit & 0xF)); 671 current_bigit >>>= 4; 672 } 673 } 674 // And finally the last bigit. 675 int most_significant_bigit = bigits_[used_digits_ - 1]; 676 while (most_significant_bigit != 0) { 677 buffer.setCharAt(string_index--, hexCharOfValue(most_significant_bigit & 0xF)); 678 most_significant_bigit >>>= 4; 679 } 680 return buffer.toString(); 681 } 682 683 684 int bigitAt(final int index) { 685 if (index >= bigitLength()) return 0; 686 if (index < exponent_) return 0; 687 return bigits_[index - exponent_]; 688 } 689 690 691 static int compare(final Bignum a, final Bignum b) { 692 assert (a.isClamped()); 693 assert (b.isClamped()); 694 final int bigit_length_a = a.bigitLength(); 695 final int bigit_length_b = b.bigitLength(); 696 if (bigit_length_a < bigit_length_b) return -1; 697 if (bigit_length_a > bigit_length_b) return +1; 698 for (int i = bigit_length_a - 1; i >= Math.min(a.exponent_, b.exponent_); --i) { 699 final int bigit_a = a.bigitAt(i); 700 final int bigit_b = b.bigitAt(i); 701 if (bigit_a < bigit_b) return -1; 702 if (bigit_a > bigit_b) return +1; 703 // Otherwise they are equal up to this digit. Try the next digit. 704 } 705 return 0; 706 } 707 708 709 static int plusCompare(final Bignum a, final Bignum b, final Bignum c) { 710 assert (a.isClamped()); 711 assert (b.isClamped()); 712 assert (c.isClamped()); 713 if (a.bigitLength() < b.bigitLength()) { 714 return plusCompare(b, a, c); 715 } 716 if (a.bigitLength() + 1 < c.bigitLength()) return -1; 717 if (a.bigitLength() > c.bigitLength()) return +1; 718 // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than 719 // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one 720 // of 'a'. 721 if (a.exponent_ >= b.bigitLength() && a.bigitLength() < c.bigitLength()) { 722 return -1; 723 } 724 725 int borrow = 0; 726 // Starting at min_exponent all digits are == 0. So no need to compare them. 727 final int min_exponent = Math.min(Math.min(a.exponent_, b.exponent_), c.exponent_); 728 for (int i = c.bigitLength() - 1; i >= min_exponent; --i) { 729 final int int_a = a.bigitAt(i); 730 final int int_b = b.bigitAt(i); 731 final int int_c = c.bigitAt(i); 732 final int sum = int_a + int_b; 733 if (sum > int_c + borrow) { 734 return +1; 735 } else { 736 borrow = int_c + borrow - sum; 737 if (borrow > 1) return -1; 738 borrow <<= kBigitSize; 739 } 740 } 741 if (borrow == 0) return 0; 742 return -1; 743 } 744 745 746 void clamp() { 747 while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) { 748 used_digits_--; 749 } 750 if (used_digits_ == 0) { 751 // Zero. 752 exponent_ = 0; 753 } 754 } 755 756 757 boolean isClamped() { 758 return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0; 759 } 760 761 762 void zero() { 763 for (int i = 0; i < used_digits_; ++i) { 764 bigits_[i] = 0; 765 } 766 used_digits_ = 0; 767 exponent_ = 0; 768 } 769 770 771 void align(final Bignum other) { 772 if (exponent_ > other.exponent_) { 773 // If "X" represents a "hidden" digit (by the exponent) then we are in the 774 // following case (a == this, b == other): 775 // a: aaaaaaXXXX or a: aaaaaXXX 776 // b: bbbbbbX b: bbbbbbbbXX 777 // We replace some of the hidden digits (X) of a with 0 digits. 778 // a: aaaaaa000X or a: aaaaa0XX 779 final int zero_digits = exponent_ - other.exponent_; 780 ensureCapacity(used_digits_ + zero_digits); 781 for (int i = used_digits_ - 1; i >= 0; --i) { 782 bigits_[i + zero_digits] = bigits_[i]; 783 } 784 for (int i = 0; i < zero_digits; ++i) { 785 bigits_[i] = 0; 786 } 787 used_digits_ += zero_digits; 788 exponent_ -= zero_digits; 789 assert (used_digits_ >= 0); 790 assert (exponent_ >= 0); 791 } 792 } 793 794 795 void bigitsShiftLeft(final int shift_amount) { 796 assert (shift_amount < kBigitSize); 797 assert (shift_amount >= 0); 798 int carry = 0; 799 for (int i = 0; i < used_digits_; ++i) { 800 final int new_carry = bigits_[i] >>> (kBigitSize - shift_amount); 801 bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask; 802 carry = new_carry; 803 } 804 if (carry != 0) { 805 bigits_[used_digits_] = carry; 806 used_digits_++; 807 } 808 } 809 810 811 void subtractTimes(final Bignum other, final int factor) { 812 assert (exponent_ <= other.exponent_); 813 if (factor < 3) { 814 for (int i = 0; i < factor; ++i) { 815 subtractBignum(other); 816 } 817 return; 818 } 819 int borrow = 0; 820 final int exponent_diff = other.exponent_ - exponent_; 821 for (int i = 0; i < other.used_digits_; ++i) { 822 final long product = ((long) factor) * other.bigits_[i]; 823 final long remove = borrow + product; 824 final int difference = bigits_[i + exponent_diff] - (int) (remove & kBigitMask); 825 bigits_[i + exponent_diff] = difference & kBigitMask; 826 borrow = (int) ((difference >>> (kChunkSize - 1)) + 827 (remove >>> kBigitSize)); 828 } 829 for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) { 830 if (borrow == 0) return; 831 final int difference = bigits_[i] - borrow; 832 bigits_[i] = difference & kBigitMask; 833 borrow = difference >>> (kChunkSize - 1); 834 } 835 clamp(); 836 } 837 838 @Override 839 public String toString() { 840 return "Bignum" + Arrays.toString(bigits_); 841 } 842 }