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 used_digits_; 80 // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize). 81 private int exponent_; 82 private final int[] bigits_ = new int[kBigitCapacity]; 83 84 Bignum() {} 85 86 void times10() { multiplyByUInt32(10); } 87 88 static boolean equal(final Bignum a, final Bignum b) { 89 return compare(a, b) == 0; 90 } 91 static boolean lessEqual(final Bignum a, final Bignum b) { 92 return compare(a, b) <= 0; 93 } 94 static boolean less(final Bignum a, final Bignum b) { 95 return compare(a, b) < 0; 96 } 97 98 // Returns a + b == c 99 static boolean plusEqual(final Bignum a, final Bignum b, final Bignum c) { 100 return plusCompare(a, b, c) == 0; 101 } 102 // Returns a + b <= c 103 static boolean plusLessEqual(final Bignum a, final Bignum b, final Bignum c) { 104 return plusCompare(a, b, c) <= 0; 105 } 106 // Returns a + b < c 107 static boolean plusLess(final Bignum a, final Bignum b, final Bignum c) { 108 return plusCompare(a, b, c) < 0; 109 } 110 111 private void ensureCapacity(final int size) { 112 if (size > kBigitCapacity) { 113 throw new RuntimeException(); 114 } 115 } 116 117 // BigitLength includes the "hidden" digits encoded in the exponent. 118 int bigitLength() { return used_digits_ + exponent_; } 119 120 // Guaranteed to lie in one Bigit. 121 void assignUInt16(final char value) { 122 assert (kBigitSize >= 16); 123 zero(); 124 if (value == 0) { 125 return; 126 } 127 128 ensureCapacity(1); 129 bigits_[0] = value; 130 used_digits_ = 1; 131 } 132 133 134 void assignUInt64(long value) { 135 final int kUInt64Size = 64; 136 137 zero(); 138 if (value == 0) { 139 return; 140 } 141 142 final int needed_bigits = kUInt64Size / kBigitSize + 1; 143 ensureCapacity(needed_bigits); 144 for (int i = 0; i < needed_bigits; ++i) { 145 bigits_[i] = (int) (value & kBigitMask); 146 value = value >>> kBigitSize; 147 } 148 used_digits_ = needed_bigits; 149 clamp(); 150 } 151 152 153 void assignBignum(final Bignum other) { 154 exponent_ = other.exponent_; 155 for (int i = 0; i < other.used_digits_; ++i) { 156 bigits_[i] = other.bigits_[i]; 157 } 158 // Clear the excess digits (if there were any). 159 for (int i = other.used_digits_; i < used_digits_; ++i) { 160 bigits_[i] = 0; 161 } 162 used_digits_ = other.used_digits_; 163 } 164 165 166 static long readUInt64(final String str, 167 final int from, 168 final int digits_to_read) { 169 long result = 0; 170 for (int i = from; i < from + digits_to_read; ++i) { 171 final int digit = str.charAt(i) - '0'; 172 assert (0 <= digit && digit <= 9); 173 result = result * 10 + digit; 174 } 175 return result; 176 } 177 178 179 void assignDecimalString(final String str) { 180 // 2^64 = 18446744073709551616 > 10^19 181 final int kMaxUint64DecimalDigits = 19; 182 zero(); 183 int length = str.length(); 184 int pos = 0; 185 // Let's just say that each digit needs 4 bits. 186 while (length >= kMaxUint64DecimalDigits) { 187 final long digits = readUInt64(str, pos, kMaxUint64DecimalDigits); 188 pos += kMaxUint64DecimalDigits; 189 length -= kMaxUint64DecimalDigits; 190 multiplyByPowerOfTen(kMaxUint64DecimalDigits); 191 addUInt64(digits); 192 } 193 final long digits = readUInt64(str, pos, length); 194 multiplyByPowerOfTen(length); 195 addUInt64(digits); 196 clamp(); 197 } 198 199 200 static int hexCharValue(final char c) { 201 if ('0' <= c && c <= '9') return c - '0'; 202 if ('a' <= c && c <= 'f') return 10 + c - 'a'; 203 assert ('A' <= c && c <= 'F'); 204 return 10 + c - 'A'; 205 } 206 207 208 void assignHexString(final String str) { 209 zero(); 210 final int length = str.length(); 211 212 final int needed_bigits = length * 4 / kBigitSize + 1; 213 ensureCapacity(needed_bigits); 214 int string_index = length - 1; 215 for (int i = 0; i < needed_bigits - 1; ++i) { 216 // These bigits are guaranteed to be "full". 217 int current_bigit = 0; 218 for (int j = 0; j < kBigitSize / 4; j++) { 219 current_bigit += hexCharValue(str.charAt(string_index--)) << (j * 4); 220 } 221 bigits_[i] = current_bigit; 222 } 223 used_digits_ = needed_bigits - 1; 224 225 int most_significant_bigit = 0; // Could be = 0; 226 for (int j = 0; j <= string_index; ++j) { 227 most_significant_bigit <<= 4; 228 most_significant_bigit += hexCharValue(str.charAt(j)); 229 } 230 if (most_significant_bigit != 0) { 231 bigits_[used_digits_] = most_significant_bigit; 232 used_digits_++; 233 } 234 clamp(); 235 } 236 237 238 void addUInt64(final long operand) { 239 if (operand == 0) return; 240 final Bignum other = new Bignum(); 241 other.assignUInt64(operand); 242 addBignum(other); 243 } 244 245 246 void addBignum(final Bignum other) { 247 assert (isClamped()); 248 assert (other.isClamped()); 249 250 // If this has a greater exponent than other append zero-bigits to this. 251 // After this call exponent_ <= other.exponent_. 252 align(other); 253 254 // There are two possibilities: 255 // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) 256 // bbbbb 00000000 257 // ---------------- 258 // ccccccccccc 0000 259 // or 260 // aaaaaaaaaa 0000 261 // bbbbbbbbb 0000000 262 // ----------------- 263 // cccccccccccc 0000 264 // In both cases we might need a carry bigit. 265 266 ensureCapacity(1 + Math.max(bigitLength(), other.bigitLength()) - exponent_); 267 int carry = 0; 268 int bigit_pos = other.exponent_ - exponent_; 269 assert (bigit_pos >= 0); 270 for (int i = 0; i < other.used_digits_; ++i) { 271 final int sum = bigits_[bigit_pos] + other.bigits_[i] + carry; 272 bigits_[bigit_pos] = sum & kBigitMask; 273 carry = sum >>> kBigitSize; 274 bigit_pos++; 275 } 276 277 while (carry != 0) { 278 final int sum = bigits_[bigit_pos] + carry; 279 bigits_[bigit_pos] = sum & kBigitMask; 280 carry = sum >>> kBigitSize; 281 bigit_pos++; 282 } 283 used_digits_ = Math.max(bigit_pos, used_digits_); 284 assert (isClamped()); 285 } 286 287 288 void subtractBignum(final Bignum other) { 289 assert (isClamped()); 290 assert (other.isClamped()); 291 // We require this to be bigger than other. 292 assert (lessEqual(other, this)); 293 294 align(other); 295 296 final int offset = other.exponent_ - exponent_; 297 int borrow = 0; 298 int i; 299 for (i = 0; i < other.used_digits_; ++i) { 300 assert ((borrow == 0) || (borrow == 1)); 301 final int difference = bigits_[i + offset] - other.bigits_[i] - borrow; 302 bigits_[i + offset] = difference & kBigitMask; 303 borrow = difference >>> (kChunkSize - 1); 304 } 305 while (borrow != 0) { 306 final int difference = bigits_[i + offset] - borrow; 307 bigits_[i + offset] = difference & kBigitMask; 308 borrow = difference >>> (kChunkSize - 1); 309 ++i; 310 } 311 clamp(); 312 } 313 314 315 void shiftLeft(final int shift_amount) { 316 if (used_digits_ == 0) return; 317 exponent_ += shift_amount / kBigitSize; 318 final int local_shift = shift_amount % kBigitSize; 319 ensureCapacity(used_digits_ + 1); 320 bigitsShiftLeft(local_shift); 321 } 322 323 324 void multiplyByUInt32(final int factor) { 325 if (factor == 1) return; 326 if (factor == 0) { 327 zero(); 328 return; 329 } 330 if (used_digits_ == 0) return; 331 332 // The product of a bigit with the factor is of size kBigitSize + 32. 333 // Assert that this number + 1 (for the carry) fits into double int. 334 assert (kDoubleChunkSize >= kBigitSize + 32 + 1); 335 long carry = 0; 336 for (int i = 0; i < used_digits_; ++i) { 337 final long product = (factor & 0xFFFFFFFFL) * bigits_[i] + carry; 338 bigits_[i] = (int) (product & kBigitMask); 339 carry = product >>> kBigitSize; 340 } 341 while (carry != 0) { 342 ensureCapacity(used_digits_ + 1); 343 bigits_[used_digits_] = (int) (carry & kBigitMask); 344 used_digits_++; 345 carry >>>= kBigitSize; 346 } 347 } 348 349 350 void multiplyByUInt64(final long factor) { 351 if (factor == 1) return; 352 if (factor == 0) { 353 zero(); 354 return; 355 } 356 assert (kBigitSize < 32); 357 long carry = 0; 358 final long low = factor & 0xFFFFFFFFL; 359 final long high = factor >>> 32; 360 for (int i = 0; i < used_digits_; ++i) { 361 final long product_low = low * bigits_[i]; 362 final long product_high = high * bigits_[i]; 363 final long tmp = (carry & kBigitMask) + product_low; 364 bigits_[i] = (int) (tmp & kBigitMask); 365 carry = (carry >>> kBigitSize) + (tmp >>> kBigitSize) + 366 (product_high << (32 - kBigitSize)); 367 } 368 while (carry != 0) { 369 ensureCapacity(used_digits_ + 1); 370 bigits_[used_digits_] = (int) (carry & kBigitMask); 371 used_digits_++; 372 carry >>>= kBigitSize; 373 } 374 } 375 376 377 void multiplyByPowerOfTen(final int exponent) { 378 final long kFive27 = 0x6765c793fa10079dL; 379 final int kFive1 = 5; 380 final int kFive2 = kFive1 * 5; 381 final int kFive3 = kFive2 * 5; 382 final int kFive4 = kFive3 * 5; 383 final int kFive5 = kFive4 * 5; 384 final int kFive6 = kFive5 * 5; 385 final int kFive7 = kFive6 * 5; 386 final int kFive8 = kFive7 * 5; 387 final int kFive9 = kFive8 * 5; 388 final int kFive10 = kFive9 * 5; 389 final int kFive11 = kFive10 * 5; 390 final int kFive12 = kFive11 * 5; 391 final int kFive13 = kFive12 * 5; 392 final int kFive1_to_12[] = 393 { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, 394 kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; 395 396 assert (exponent >= 0); 397 if (exponent == 0) return; 398 if (used_digits_ == 0) return; 399 400 // We shift by exponent at the end just before returning. 401 int remaining_exponent = exponent; 402 while (remaining_exponent >= 27) { 403 multiplyByUInt64(kFive27); 404 remaining_exponent -= 27; 405 } 406 while (remaining_exponent >= 13) { 407 multiplyByUInt32(kFive13); 408 remaining_exponent -= 13; 409 } 410 if (remaining_exponent > 0) { 411 multiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); 412 } 413 shiftLeft(exponent); 414 } 415 416 417 void square() { 418 assert (isClamped()); 419 final int product_length = 2 * used_digits_; 420 ensureCapacity(product_length); 421 422 // Comba multiplication: compute each column separately. 423 // Example: r = a2a1a0 * b2b1b0. 424 // r = 1 * a0b0 + 425 // 10 * (a1b0 + a0b1) + 426 // 100 * (a2b0 + a1b1 + a0b2) + 427 // 1000 * (a2b1 + a1b2) + 428 // 10000 * a2b2 429 // 430 // In the worst case we have to accumulate nb-digits products of digit*digit. 431 // 432 // Assert that the additional number of bits in a DoubleChunk are enough to 433 // sum up used_digits of Bigit*Bigit. 434 if ((1L << (2 * (kChunkSize - kBigitSize))) <= used_digits_) { 435 throw new RuntimeException("unimplemented"); 436 } 437 long accumulator = 0; 438 // First shift the digits so we don't overwrite them. 439 final int copy_offset = used_digits_; 440 for (int i = 0; i < used_digits_; ++i) { 441 bigits_[copy_offset + i] = bigits_[i]; 442 } 443 // We have two loops to avoid some 'if's in the loop. 444 for (int i = 0; i < used_digits_; ++i) { 445 // Process temporary digit i with power i. 446 // The sum of the two indices must be equal to i. 447 int bigit_index1 = i; 448 int bigit_index2 = 0; 449 // Sum all of the sub-products. 450 while (bigit_index1 >= 0) { 451 final int int1 = bigits_[copy_offset + bigit_index1]; 452 final int int2 = bigits_[copy_offset + bigit_index2]; 453 accumulator += ((long) int1) * int2; 454 bigit_index1--; 455 bigit_index2++; 456 } 457 bigits_[i] = (int) (accumulator & kBigitMask); 458 accumulator >>>= kBigitSize; 459 } 460 for (int i = used_digits_; i < product_length; ++i) { 461 int bigit_index1 = used_digits_ - 1; 462 int bigit_index2 = i - bigit_index1; 463 // Invariant: sum of both indices is again equal to i. 464 // Inner loop runs 0 times on last iteration, emptying accumulator. 465 while (bigit_index2 < used_digits_) { 466 final int int1 = bigits_[copy_offset + bigit_index1]; 467 final int int2 = bigits_[copy_offset + bigit_index2]; 468 accumulator += ((long) int1) * int2; 469 bigit_index1--; 470 bigit_index2++; 471 } 472 // The overwritten bigits_[i] will never be read in further loop iterations, 473 // because bigit_index1 and bigit_index2 are always greater 474 // than i - used_digits_. 475 bigits_[i] = (int) (accumulator & kBigitMask); 476 accumulator >>>= kBigitSize; 477 } 478 // Since the result was guaranteed to lie inside the number the 479 // accumulator must be 0 now. 480 assert (accumulator == 0); 481 482 // Don't forget to update the used_digits and the exponent. 483 used_digits_ = product_length; 484 exponent_ *= 2; 485 clamp(); 486 } 487 488 489 void assignPowerUInt16(int base, final int power_exponent) { 490 assert (base != 0); 491 assert (power_exponent >= 0); 492 if (power_exponent == 0) { 493 assignUInt16((char) 1); 494 return; 495 } 496 zero(); 497 int shifts = 0; 498 // We expect base to be in range 2-32, and most often to be 10. 499 // It does not make much sense to implement different algorithms for counting 500 // the bits. 501 while ((base & 1) == 0) { 502 base >>>= 1; 503 shifts++; 504 } 505 int bit_size = 0; 506 int tmp_base = base; 507 while (tmp_base != 0) { 508 tmp_base >>>= 1; 509 bit_size++; 510 } 511 final int final_size = bit_size * power_exponent; 512 // 1 extra bigit for the shifting, and one for rounded final_size. 513 ensureCapacity(final_size / kBigitSize + 2); 514 515 // Left to Right exponentiation. 516 int mask = 1; 517 while (power_exponent >= mask) mask <<= 1; 518 519 // The mask is now pointing to the bit above the most significant 1-bit of 520 // power_exponent. 521 // Get rid of first 1-bit; 522 mask >>>= 2; 523 long this_value = base; 524 525 boolean delayed_multiplication = false; 526 final long max_32bits = 0xFFFFFFFFL; 527 while (mask != 0 && this_value <= max_32bits) { 528 this_value = this_value * this_value; 529 // Verify that there is enough space in this_value to perform the 530 // multiplication. The first bit_size bits must be 0. 531 if ((power_exponent & mask) != 0) { 532 assert bit_size > 0; 533 final long base_bits_mask = 534 ~((1L << (64 - bit_size)) - 1); 535 final boolean high_bits_zero = (this_value & base_bits_mask) == 0; 536 if (high_bits_zero) { 537 this_value *= base; 538 } else { 539 delayed_multiplication = true; 540 } 541 } 542 mask >>>= 1; 543 } 544 assignUInt64(this_value); 545 if (delayed_multiplication) { 546 multiplyByUInt32(base); 547 } 548 549 // Now do the same thing as a bignum. 550 while (mask != 0) { 551 square(); 552 if ((power_exponent & mask) != 0) { 553 multiplyByUInt32(base); 554 } 555 mask >>>= 1; 556 } 557 558 // And finally add the saved shifts. 559 shiftLeft(shifts * power_exponent); 560 } 561 562 563 // Precondition: this/other < 16bit. 564 char divideModuloIntBignum(final Bignum other) { 565 assert (isClamped()); 566 assert (other.isClamped()); 567 assert (other.used_digits_ > 0); 568 569 // Easy case: if we have less digits than the divisor than the result is 0. 570 // Note: this handles the case where this == 0, too. 571 if (bigitLength() < other.bigitLength()) { 572 return 0; 573 } 574 575 align(other); 576 577 char result = 0; 578 579 // Start by removing multiples of 'other' until both numbers have the same 580 // number of digits. 581 while (bigitLength() > other.bigitLength()) { 582 // This naive approach is extremely inefficient if `this` divided by other 583 // is big. This function is implemented for doubleToString where 584 // the result should be small (less than 10). 585 assert (other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16)); 586 assert (bigits_[used_digits_ - 1] < 0x10000); 587 // Remove the multiples of the first digit. 588 // Example this = 23 and other equals 9. -> Remove 2 multiples. 589 result += (bigits_[used_digits_ - 1]); 590 subtractTimes(other, bigits_[used_digits_ - 1]); 591 } 592 593 assert (bigitLength() == other.bigitLength()); 594 595 // Both bignums are at the same length now. 596 // Since other has more than 0 digits we know that the access to 597 // bigits_[used_digits_ - 1] is safe. 598 final int this_bigit = bigits_[used_digits_ - 1]; 599 final int other_bigit = other.bigits_[other.used_digits_ - 1]; 600 601 if (other.used_digits_ == 1) { 602 // Shortcut for easy (and common) case. 603 final int quotient = Integer.divideUnsigned(this_bigit, other_bigit); 604 bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient; 605 assert (Integer.compareUnsigned(quotient, 0x10000) < 0); 606 result += quotient; 607 clamp(); 608 return result; 609 } 610 611 final int division_estimate = Integer.divideUnsigned(this_bigit, (other_bigit + 1)); 612 assert (Integer.compareUnsigned(division_estimate, 0x10000) < 0); 613 result += division_estimate; 614 subtractTimes(other, division_estimate); 615 616 if (other_bigit * (division_estimate + 1) > this_bigit) { 617 // No need to even try to subtract. Even if other's remaining digits were 0 618 // another subtraction would be too much. 619 return result; 620 } 621 622 while (lessEqual(other, this)) { 623 subtractBignum(other); 624 result++; 625 } 626 return result; 627 } 628 629 630 static int sizeInHexChars(int number) { 631 assert (number > 0); 632 int result = 0; 633 while (number != 0) { 634 number >>>= 4; 635 result++; 636 } 637 return result; 638 } 639 640 641 static char hexCharOfValue(final int value) { 642 assert (0 <= value && value <= 16); 643 if (value < 10) return (char) (value + '0'); 644 return (char) (value - 10 + 'A'); 645 } 646 647 648 String toHexString() { 649 assert (isClamped()); 650 // Each bigit must be printable as separate hex-character. 651 assert (kBigitSize % 4 == 0); 652 final int kHexCharsPerBigit = kBigitSize / 4; 653 654 if (used_digits_ == 0) { 655 return "0"; 656 } 657 658 final int needed_chars = (bigitLength() - 1) * kHexCharsPerBigit + 659 sizeInHexChars(bigits_[used_digits_ - 1]); 660 final StringBuilder buffer = new StringBuilder(needed_chars); 661 buffer.setLength(needed_chars); 662 663 int string_index = needed_chars - 1; 664 for (int i = 0; i < exponent_; ++i) { 665 for (int j = 0; j < kHexCharsPerBigit; ++j) { 666 buffer.setCharAt(string_index--, '0'); 667 } 668 } 669 for (int i = 0; i < used_digits_ - 1; ++i) { 670 int current_bigit = bigits_[i]; 671 for (int j = 0; j < kHexCharsPerBigit; ++j) { 672 buffer.setCharAt(string_index--, hexCharOfValue(current_bigit & 0xF)); 673 current_bigit >>>= 4; 674 } 675 } 676 // And finally the last bigit. 677 int most_significant_bigit = bigits_[used_digits_ - 1]; 678 while (most_significant_bigit != 0) { 679 buffer.setCharAt(string_index--, hexCharOfValue(most_significant_bigit & 0xF)); 680 most_significant_bigit >>>= 4; 681 } 682 return buffer.toString(); 683 } 684 685 686 int bigitOrZero(final int index) { 687 if (index >= bigitLength()) return 0; 688 if (index < exponent_) return 0; 689 return bigits_[index - exponent_]; 690 } 691 692 693 static int compare(final Bignum a, final Bignum b) { 694 assert (a.isClamped()); 695 assert (b.isClamped()); 696 final int bigit_length_a = a.bigitLength(); 697 final int bigit_length_b = b.bigitLength(); 698 if (bigit_length_a < bigit_length_b) return -1; 699 if (bigit_length_a > bigit_length_b) return +1; 700 for (int i = bigit_length_a - 1; i >= Math.min(a.exponent_, b.exponent_); --i) { 701 final int bigit_a = a.bigitOrZero(i); 702 final int bigit_b = b.bigitOrZero(i); 703 if (bigit_a < bigit_b) return -1; 704 if (bigit_a > bigit_b) return +1; 705 // Otherwise they are equal up to this digit. Try the next digit. 706 } 707 return 0; 708 } 709 710 711 static int plusCompare(final Bignum a, final Bignum b, final Bignum c) { 712 assert (a.isClamped()); 713 assert (b.isClamped()); 714 assert (c.isClamped()); 715 if (a.bigitLength() < b.bigitLength()) { 716 return plusCompare(b, a, c); 717 } 718 if (a.bigitLength() + 1 < c.bigitLength()) return -1; 719 if (a.bigitLength() > c.bigitLength()) return +1; 720 // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than 721 // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one 722 // of 'a'. 723 if (a.exponent_ >= b.bigitLength() && a.bigitLength() < c.bigitLength()) { 724 return -1; 725 } 726 727 int borrow = 0; 728 // Starting at min_exponent all digits are == 0. So no need to compare them. 729 final int min_exponent = Math.min(Math.min(a.exponent_, b.exponent_), c.exponent_); 730 for (int i = c.bigitLength() - 1; i >= min_exponent; --i) { 731 final int int_a = a.bigitOrZero(i); 732 final int int_b = b.bigitOrZero(i); 733 final int int_c = c.bigitOrZero(i); 734 final int sum = int_a + int_b; 735 if (sum > int_c + borrow) { 736 return +1; 737 } else { 738 borrow = int_c + borrow - sum; 739 if (borrow > 1) return -1; 740 borrow <<= kBigitSize; 741 } 742 } 743 if (borrow == 0) return 0; 744 return -1; 745 } 746 747 748 void clamp() { 749 while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) { 750 used_digits_--; 751 } 752 if (used_digits_ == 0) { 753 // Zero. 754 exponent_ = 0; 755 } 756 } 757 758 759 boolean isClamped() { 760 return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0; 761 } 762 763 764 void zero() { 765 for (int i = 0; i < used_digits_; ++i) { 766 bigits_[i] = 0; 767 } 768 used_digits_ = 0; 769 exponent_ = 0; 770 } 771 772 773 void align(final Bignum other) { 774 if (exponent_ > other.exponent_) { 775 // If "X" represents a "hidden" digit (by the exponent) then we are in the 776 // following case (a == this, b == other): 777 // a: aaaaaaXXXX or a: aaaaaXXX 778 // b: bbbbbbX b: bbbbbbbbXX 779 // We replace some of the hidden digits (X) of a with 0 digits. 780 // a: aaaaaa000X or a: aaaaa0XX 781 final int zero_digits = exponent_ - other.exponent_; 782 ensureCapacity(used_digits_ + zero_digits); 783 for (int i = used_digits_ - 1; i >= 0; --i) { 784 bigits_[i + zero_digits] = bigits_[i]; 785 } 786 for (int i = 0; i < zero_digits; ++i) { 787 bigits_[i] = 0; 788 } 789 used_digits_ += zero_digits; 790 exponent_ -= zero_digits; 791 assert (used_digits_ >= 0); 792 assert (exponent_ >= 0); 793 } 794 } 795 796 797 void bigitsShiftLeft(final int shift_amount) { 798 assert (shift_amount < kBigitSize); 799 assert (shift_amount >= 0); 800 int carry = 0; 801 for (int i = 0; i < used_digits_; ++i) { 802 final int new_carry = bigits_[i] >>> (kBigitSize - shift_amount); 803 bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask; 804 carry = new_carry; 805 } 806 if (carry != 0) { 807 bigits_[used_digits_] = carry; 808 used_digits_++; 809 } 810 } 811 812 813 void subtractTimes(final Bignum other, final int factor) { 814 assert (exponent_ <= other.exponent_); 815 if (factor < 3) { 816 for (int i = 0; i < factor; ++i) { 817 subtractBignum(other); 818 } 819 return; 820 } 821 int borrow = 0; 822 final int exponent_diff = other.exponent_ - exponent_; 823 for (int i = 0; i < other.used_digits_; ++i) { 824 final long product = ((long) factor) * other.bigits_[i]; 825 final long remove = borrow + product; 826 final int difference = bigits_[i + exponent_diff] - (int) (remove & kBigitMask); 827 bigits_[i + exponent_diff] = difference & kBigitMask; 828 borrow = (int) ((difference >>> (kChunkSize - 1)) + 829 (remove >>> kBigitSize)); 830 } 831 for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) { 832 if (borrow == 0) return; 833 final int difference = bigits_[i] - borrow; 834 bigits_[i] = difference & kBigitMask; 835 borrow = difference >>> (kChunkSize - 1); 836 } 837 clamp(); 838 } 839 840 @Override 841 public String toString() { 842 return "Bignum" + Arrays.toString(bigits_); 843 } 844 }