1<?php 2 3/** 4 * Pure-PHP BigInteger Engine 5 * 6 * PHP version 5 and 7 7 * 8 * @author Jim Wigginton <terrafrost@php.net> 9 * @copyright 2017 Jim Wigginton 10 * @license http://www.opensource.org/licenses/mit-license.html MIT License 11 * @link http://pear.php.net/package/Math_BigInteger 12 */ 13 14namespace phpseclib3\Math\BigInteger\Engines; 15 16use phpseclib3\Common\Functions\Strings; 17use phpseclib3\Exception\BadConfigurationException; 18 19/** 20 * Pure-PHP Engine. 21 * 22 * @author Jim Wigginton <terrafrost@php.net> 23 */ 24abstract class PHP extends Engine 25{ 26 /**#@+ 27 * Array constants 28 * 29 * Rather than create a thousands and thousands of new BigInteger objects in repeated function calls to add() and 30 * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them. 31 * 32 */ 33 /** 34 * $result[self::VALUE] contains the value. 35 */ 36 const VALUE = 0; 37 /** 38 * $result[self::SIGN] contains the sign. 39 */ 40 const SIGN = 1; 41 /**#@-*/ 42 43 /** 44 * Karatsuba Cutoff 45 * 46 * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication? 47 * 48 */ 49 const KARATSUBA_CUTOFF = 25; 50 51 /** 52 * Can Bitwise operations be done fast? 53 * 54 * @see parent::bitwise_leftRotate() 55 * @see parent::bitwise_rightRotate() 56 */ 57 const FAST_BITWISE = true; 58 59 /** 60 * Engine Directory 61 * 62 * @see parent::setModExpEngine 63 */ 64 const ENGINE_DIR = 'PHP'; 65 66 /** 67 * Default constructor 68 * 69 * @param mixed $x integer Base-10 number or base-$base number if $base set. 70 * @param int $base 71 * @return PHP 72 * @see parent::__construct() 73 */ 74 public function __construct($x = 0, $base = 10) 75 { 76 if (!isset(static::$isValidEngine[static::class])) { 77 static::$isValidEngine[static::class] = static::isValidEngine(); 78 } 79 if (!static::$isValidEngine[static::class]) { 80 throw new BadConfigurationException(static::class . ' is not setup correctly on this system'); 81 } 82 83 $this->value = []; 84 parent::__construct($x, $base); 85 } 86 87 /** 88 * Initialize a PHP BigInteger Engine instance 89 * 90 * @param int $base 91 * @see parent::__construct() 92 */ 93 protected function initialize($base) 94 { 95 switch (abs($base)) { 96 case 16: 97 $x = (strlen($this->value) & 1) ? '0' . $this->value : $this->value; 98 $temp = new static(Strings::hex2bin($x), 256); 99 $this->value = $temp->value; 100 break; 101 case 10: 102 $temp = new static(); 103 104 $multiplier = new static(); 105 $multiplier->value = [static::MAX10]; 106 107 $x = $this->value; 108 109 if ($x[0] == '-') { 110 $this->is_negative = true; 111 $x = substr($x, 1); 112 } 113 114 $x = str_pad( 115 $x, 116 strlen($x) + ((static::MAX10LEN - 1) * strlen($x)) % static::MAX10LEN, 117 0, 118 STR_PAD_LEFT 119 ); 120 while (strlen($x)) { 121 $temp = $temp->multiply($multiplier); 122 $temp = $temp->add(new static($this->int2bytes(substr($x, 0, static::MAX10LEN)), 256)); 123 $x = substr($x, static::MAX10LEN); 124 } 125 126 $this->value = $temp->value; 127 } 128 } 129 130 /** 131 * Pads strings so that unpack may be used on them 132 * 133 * @param string $str 134 * @return string 135 */ 136 protected function pad($str) 137 { 138 $length = strlen($str); 139 140 $pad = 4 - (strlen($str) % 4); 141 142 return str_pad($str, $length + $pad, "\0", STR_PAD_LEFT); 143 } 144 145 /** 146 * Converts a BigInteger to a base-10 number. 147 * 148 * @return string 149 */ 150 public function toString() 151 { 152 if (!count($this->value)) { 153 return '0'; 154 } 155 156 $temp = clone $this; 157 $temp->bitmask = false; 158 $temp->is_negative = false; 159 160 $divisor = new static(); 161 $divisor->value = [static::MAX10]; 162 $result = ''; 163 while (count($temp->value)) { 164 list($temp, $mod) = $temp->divide($divisor); 165 $result = str_pad( 166 isset($mod->value[0]) ? $mod->value[0] : '', 167 static::MAX10LEN, 168 '0', 169 STR_PAD_LEFT 170 ) . $result; 171 } 172 $result = ltrim($result, '0'); 173 if (empty($result)) { 174 $result = '0'; 175 } 176 177 if ($this->is_negative) { 178 $result = '-' . $result; 179 } 180 181 return $result; 182 } 183 184 /** 185 * Converts a BigInteger to a byte string (eg. base-256). 186 * 187 * @param bool $twos_compliment 188 * @return string 189 */ 190 public function toBytes($twos_compliment = false) 191 { 192 if ($twos_compliment) { 193 return $this->toBytesHelper(); 194 } 195 196 if (!count($this->value)) { 197 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; 198 } 199 200 $result = $this->bitwise_small_split(8); 201 $result = implode('', array_map('chr', $result)); 202 203 return $this->precision > 0 ? 204 str_pad( 205 substr($result, -(($this->precision + 7) >> 3)), 206 ($this->precision + 7) >> 3, 207 chr(0), 208 STR_PAD_LEFT 209 ) : 210 $result; 211 } 212 213 /** 214 * Performs addition. 215 * 216 * @param array $x_value 217 * @param bool $x_negative 218 * @param array $y_value 219 * @param bool $y_negative 220 * @return array 221 */ 222 protected static function addHelper(array $x_value, $x_negative, array $y_value, $y_negative) 223 { 224 $x_size = count($x_value); 225 $y_size = count($y_value); 226 227 if ($x_size == 0) { 228 return [ 229 self::VALUE => $y_value, 230 self::SIGN => $y_negative 231 ]; 232 } elseif ($y_size == 0) { 233 return [ 234 self::VALUE => $x_value, 235 self::SIGN => $x_negative 236 ]; 237 } 238 239 // subtract, if appropriate 240 if ($x_negative != $y_negative) { 241 if ($x_value == $y_value) { 242 return [ 243 self::VALUE => [], 244 self::SIGN => false 245 ]; 246 } 247 248 $temp = self::subtractHelper($x_value, false, $y_value, false); 249 $temp[self::SIGN] = self::compareHelper($x_value, false, $y_value, false) > 0 ? 250 $x_negative : $y_negative; 251 252 return $temp; 253 } 254 255 if ($x_size < $y_size) { 256 $size = $x_size; 257 $value = $y_value; 258 } else { 259 $size = $y_size; 260 $value = $x_value; 261 } 262 263 $value[count($value)] = 0; // just in case the carry adds an extra digit 264 265 $carry = 0; 266 for ($i = 0, $j = 1; $j < $size; $i += 2, $j += 2) { 267 //$sum = $x_value[$j] * static::BASE_FULL + $x_value[$i] + $y_value[$j] * static::BASE_FULL + $y_value[$i] + $carry; 268 $sum = ($x_value[$j] + $y_value[$j]) * static::BASE_FULL + $x_value[$i] + $y_value[$i] + $carry; 269 $carry = $sum >= static::MAX_DIGIT2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1 270 $sum = $carry ? $sum - static::MAX_DIGIT2 : $sum; 271 272 $temp = static::BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31); 273 274 $value[$i] = (int)($sum - static::BASE_FULL * $temp); // eg. a faster alternative to fmod($sum, 0x4000000) 275 $value[$j] = $temp; 276 } 277 278 if ($j == $size) { // ie. if $y_size is odd 279 $sum = $x_value[$i] + $y_value[$i] + $carry; 280 $carry = $sum >= static::BASE_FULL; 281 $value[$i] = $carry ? $sum - static::BASE_FULL : $sum; 282 ++$i; // ie. let $i = $j since we've just done $value[$i] 283 } 284 285 if ($carry) { 286 for (; $value[$i] == static::MAX_DIGIT; ++$i) { 287 $value[$i] = 0; 288 } 289 ++$value[$i]; 290 } 291 292 return [ 293 self::VALUE => self::trim($value), 294 self::SIGN => $x_negative 295 ]; 296 } 297 298 /** 299 * Performs subtraction. 300 * 301 * @param array $x_value 302 * @param bool $x_negative 303 * @param array $y_value 304 * @param bool $y_negative 305 * @return array 306 */ 307 public static function subtractHelper(array $x_value, $x_negative, array $y_value, $y_negative) 308 { 309 $x_size = count($x_value); 310 $y_size = count($y_value); 311 312 if ($x_size == 0) { 313 return [ 314 self::VALUE => $y_value, 315 self::SIGN => !$y_negative 316 ]; 317 } elseif ($y_size == 0) { 318 return [ 319 self::VALUE => $x_value, 320 self::SIGN => $x_negative 321 ]; 322 } 323 324 // add, if appropriate (ie. -$x - +$y or +$x - -$y) 325 if ($x_negative != $y_negative) { 326 $temp = self::addHelper($x_value, false, $y_value, false); 327 $temp[self::SIGN] = $x_negative; 328 329 return $temp; 330 } 331 332 $diff = self::compareHelper($x_value, $x_negative, $y_value, $y_negative); 333 334 if (!$diff) { 335 return [ 336 self::VALUE => [], 337 self::SIGN => false 338 ]; 339 } 340 341 // switch $x and $y around, if appropriate. 342 if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) { 343 $temp = $x_value; 344 $x_value = $y_value; 345 $y_value = $temp; 346 347 $x_negative = !$x_negative; 348 349 $x_size = count($x_value); 350 $y_size = count($y_value); 351 } 352 353 // at this point, $x_value should be at least as big as - if not bigger than - $y_value 354 355 $carry = 0; 356 for ($i = 0, $j = 1; $j < $y_size; $i += 2, $j += 2) { 357 $sum = ($x_value[$j] - $y_value[$j]) * static::BASE_FULL + $x_value[$i] - $y_value[$i] - $carry; 358 359 $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1 360 $sum = $carry ? $sum + static::MAX_DIGIT2 : $sum; 361 362 $temp = static::BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31); 363 364 $x_value[$i] = (int)($sum - static::BASE_FULL * $temp); 365 $x_value[$j] = $temp; 366 } 367 368 if ($j == $y_size) { // ie. if $y_size is odd 369 $sum = $x_value[$i] - $y_value[$i] - $carry; 370 $carry = $sum < 0; 371 $x_value[$i] = $carry ? $sum + static::BASE_FULL : $sum; 372 ++$i; 373 } 374 375 if ($carry) { 376 for (; !$x_value[$i]; ++$i) { 377 $x_value[$i] = static::MAX_DIGIT; 378 } 379 --$x_value[$i]; 380 } 381 382 return [ 383 self::VALUE => self::trim($x_value), 384 self::SIGN => $x_negative 385 ]; 386 } 387 388 /** 389 * Performs multiplication. 390 * 391 * @param array $x_value 392 * @param bool $x_negative 393 * @param array $y_value 394 * @param bool $y_negative 395 * @return array 396 */ 397 protected static function multiplyHelper(array $x_value, $x_negative, array $y_value, $y_negative) 398 { 399 //if ( $x_value == $y_value ) { 400 // return [ 401 // self::VALUE => self::square($x_value), 402 // self::SIGN => $x_sign != $y_value 403 // ]; 404 //} 405 406 $x_length = count($x_value); 407 $y_length = count($y_value); 408 409 if (!$x_length || !$y_length) { // a 0 is being multiplied 410 return [ 411 self::VALUE => [], 412 self::SIGN => false 413 ]; 414 } 415 416 return [ 417 self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ? 418 self::trim(self::regularMultiply($x_value, $y_value)) : 419 self::trim(self::karatsuba($x_value, $y_value)), 420 self::SIGN => $x_negative != $y_negative 421 ]; 422 } 423 424 /** 425 * Performs Karatsuba multiplication on two BigIntegers 426 * 427 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and 428 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}. 429 * 430 * @param array $x_value 431 * @param array $y_value 432 * @return array 433 */ 434 private static function karatsuba(array $x_value, array $y_value) 435 { 436 $m = min(count($x_value) >> 1, count($y_value) >> 1); 437 438 if ($m < self::KARATSUBA_CUTOFF) { 439 return self::regularMultiply($x_value, $y_value); 440 } 441 442 $x1 = array_slice($x_value, $m); 443 $x0 = array_slice($x_value, 0, $m); 444 $y1 = array_slice($y_value, $m); 445 $y0 = array_slice($y_value, 0, $m); 446 447 $z2 = self::karatsuba($x1, $y1); 448 $z0 = self::karatsuba($x0, $y0); 449 450 $z1 = self::addHelper($x1, false, $x0, false); 451 $temp = self::addHelper($y1, false, $y0, false); 452 $z1 = self::karatsuba($z1[self::VALUE], $temp[self::VALUE]); 453 $temp = self::addHelper($z2, false, $z0, false); 454 $z1 = self::subtractHelper($z1, false, $temp[self::VALUE], false); 455 456 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); 457 $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]); 458 459 $xy = self::addHelper($z2, false, $z1[self::VALUE], $z1[self::SIGN]); 460 $xy = self::addHelper($xy[self::VALUE], $xy[self::SIGN], $z0, false); 461 462 return $xy[self::VALUE]; 463 } 464 465 /** 466 * Performs long multiplication on two BigIntegers 467 * 468 * Modeled after 'multiply' in MutableBigInteger.java. 469 * 470 * @param array $x_value 471 * @param array $y_value 472 * @return array 473 */ 474 protected static function regularMultiply(array $x_value, array $y_value) 475 { 476 $x_length = count($x_value); 477 $y_length = count($y_value); 478 479 if (!$x_length || !$y_length) { // a 0 is being multiplied 480 return []; 481 } 482 483 $product_value = self::array_repeat(0, $x_length + $y_length); 484 485 // the following for loop could be removed if the for loop following it 486 // (the one with nested for loops) initially set $i to 0, but 487 // doing so would also make the result in one set of unnecessary adds, 488 // since on the outermost loops first pass, $product->value[$k] is going 489 // to always be 0 490 491 $carry = 0; 492 for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0 493 $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0 494 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 495 $product_value[$j] = (int)($temp - static::BASE_FULL * $carry); 496 } 497 498 $product_value[$j] = $carry; 499 500 // the above for loop is what the previous comment was talking about. the 501 // following for loop is the "one with nested for loops" 502 for ($i = 1; $i < $y_length; ++$i) { 503 $carry = 0; 504 505 for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) { 506 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry; 507 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 508 $product_value[$k] = (int)($temp - static::BASE_FULL * $carry); 509 } 510 511 $product_value[$k] = $carry; 512 } 513 514 return $product_value; 515 } 516 517 /** 518 * Divides two BigIntegers. 519 * 520 * Returns an array whose first element contains the quotient and whose second element contains the 521 * "common residue". If the remainder would be positive, the "common residue" and the remainder are the 522 * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder 523 * and the divisor (basically, the "common residue" is the first positive modulo). 524 * 525 * @return array{static, static} 526 * @internal This function is based off of 527 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}. 528 */ 529 protected function divideHelper(PHP $y) 530 { 531 if (count($y->value) == 1) { 532 list($q, $r) = $this->divide_digit($this->value, $y->value[0]); 533 $quotient = new static(); 534 $remainder = new static(); 535 $quotient->value = $q; 536 if ($this->is_negative) { 537 $r = $y->value[0] - $r; 538 } 539 $remainder->value = [$r]; 540 $quotient->is_negative = $this->is_negative != $y->is_negative; 541 return [$this->normalize($quotient), $this->normalize($remainder)]; 542 } 543 544 $x = clone $this; 545 $y = clone $y; 546 547 $x_sign = $x->is_negative; 548 $y_sign = $y->is_negative; 549 550 $x->is_negative = $y->is_negative = false; 551 552 $diff = $x->compare($y); 553 554 if (!$diff) { 555 $temp = new static(); 556 $temp->value = [1]; 557 $temp->is_negative = $x_sign != $y_sign; 558 return [$this->normalize($temp), $this->normalize(static::$zero[static::class])]; 559 } 560 561 if ($diff < 0) { 562 // if $x is negative, "add" $y. 563 if ($x_sign) { 564 $x = $y->subtract($x); 565 } 566 return [$this->normalize(static::$zero[static::class]), $this->normalize($x)]; 567 } 568 569 // normalize $x and $y as described in HAC 14.23 / 14.24 570 $msb = $y->value[count($y->value) - 1]; 571 for ($shift = 0; !($msb & static::MSB); ++$shift) { 572 $msb <<= 1; 573 } 574 $x->lshift($shift); 575 $y->lshift($shift); 576 $y_value = &$y->value; 577 578 $x_max = count($x->value) - 1; 579 $y_max = count($y->value) - 1; 580 581 $quotient = new static(); 582 $quotient_value = &$quotient->value; 583 $quotient_value = self::array_repeat(0, $x_max - $y_max + 1); 584 585 static $temp, $lhs, $rhs; 586 if (!isset($temp)) { 587 $temp = new static(); 588 $lhs = new static(); 589 $rhs = new static(); 590 } 591 if (static::class != get_class($temp)) { 592 $temp = new static(); 593 $lhs = new static(); 594 $rhs = new static(); 595 } 596 $temp_value = &$temp->value; 597 $rhs_value = &$rhs->value; 598 599 // $temp = $y << ($x_max - $y_max-1) in base 2**26 600 $temp_value = array_merge(self::array_repeat(0, $x_max - $y_max), $y_value); 601 602 while ($x->compare($temp) >= 0) { 603 // calculate the "common residue" 604 ++$quotient_value[$x_max - $y_max]; 605 $x = $x->subtract($temp); 606 $x_max = count($x->value) - 1; 607 } 608 609 for ($i = $x_max; $i >= $y_max + 1; --$i) { 610 $x_value = &$x->value; 611 $x_window = [ 612 isset($x_value[$i]) ? $x_value[$i] : 0, 613 isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0, 614 isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0 615 ]; 616 $y_window = [ 617 $y_value[$y_max], 618 ($y_max > 0) ? $y_value[$y_max - 1] : 0 619 ]; 620 621 $q_index = $i - $y_max - 1; 622 if ($x_window[0] == $y_window[0]) { 623 $quotient_value[$q_index] = static::MAX_DIGIT; 624 } else { 625 $quotient_value[$q_index] = self::safe_divide( 626 $x_window[0] * static::BASE_FULL + $x_window[1], 627 $y_window[0] 628 ); 629 } 630 631 $temp_value = [$y_window[1], $y_window[0]]; 632 633 $lhs->value = [$quotient_value[$q_index]]; 634 $lhs = $lhs->multiply($temp); 635 636 $rhs_value = [$x_window[2], $x_window[1], $x_window[0]]; 637 638 while ($lhs->compare($rhs) > 0) { 639 --$quotient_value[$q_index]; 640 641 $lhs->value = [$quotient_value[$q_index]]; 642 $lhs = $lhs->multiply($temp); 643 } 644 645 $adjust = self::array_repeat(0, $q_index); 646 $temp_value = [$quotient_value[$q_index]]; 647 $temp = $temp->multiply($y); 648 $temp_value = &$temp->value; 649 if (count($temp_value)) { 650 $temp_value = array_merge($adjust, $temp_value); 651 } 652 653 $x = $x->subtract($temp); 654 655 if ($x->compare(static::$zero[static::class]) < 0) { 656 $temp_value = array_merge($adjust, $y_value); 657 $x = $x->add($temp); 658 659 --$quotient_value[$q_index]; 660 } 661 662 $x_max = count($x_value) - 1; 663 } 664 665 // unnormalize the remainder 666 $x->rshift($shift); 667 668 $quotient->is_negative = $x_sign != $y_sign; 669 670 // calculate the "common residue", if appropriate 671 if ($x_sign) { 672 $y->rshift($shift); 673 $x = $y->subtract($x); 674 } 675 676 return [$this->normalize($quotient), $this->normalize($x)]; 677 } 678 679 /** 680 * Divides a BigInteger by a regular integer 681 * 682 * abc / x = a00 / x + b0 / x + c / x 683 * 684 * @param array $dividend 685 * @param int $divisor 686 * @return array 687 */ 688 private static function divide_digit(array $dividend, $divisor) 689 { 690 $carry = 0; 691 $result = []; 692 693 for ($i = count($dividend) - 1; $i >= 0; --$i) { 694 $temp = static::BASE_FULL * $carry + $dividend[$i]; 695 $result[$i] = self::safe_divide($temp, $divisor); 696 $carry = (int)($temp - $divisor * $result[$i]); 697 } 698 699 return [$result, $carry]; 700 } 701 702 /** 703 * Single digit division 704 * 705 * Even if int64 is being used the division operator will return a float64 value 706 * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't 707 * have the precision of int64 this is a problem so, when int64 is being used, 708 * we'll guarantee that the dividend is divisible by first subtracting the remainder. 709 * 710 * @param int $x 711 * @param int $y 712 * @return int 713 */ 714 private static function safe_divide($x, $y) 715 { 716 if (static::BASE === 26) { 717 return (int)($x / $y); 718 } 719 720 // static::BASE === 31 721 /** @var int */ 722 return ($x - ($x % $y)) / $y; 723 } 724 725 /** 726 * Convert an array / boolean to a PHP BigInteger object 727 * 728 * @param array $arr 729 * @return static 730 */ 731 protected function convertToObj(array $arr) 732 { 733 $result = new static(); 734 $result->value = $arr[self::VALUE]; 735 $result->is_negative = $arr[self::SIGN]; 736 737 return $this->normalize($result); 738 } 739 740 /** 741 * Normalize 742 * 743 * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision 744 * 745 * @param PHP $result 746 * @return static 747 */ 748 protected function normalize(PHP $result) 749 { 750 $result->precision = $this->precision; 751 $result->bitmask = $this->bitmask; 752 753 $value = &$result->value; 754 755 if (!count($value)) { 756 $result->is_negative = false; 757 return $result; 758 } 759 760 $value = static::trim($value); 761 762 if (!empty($result->bitmask->value)) { 763 $length = min(count($value), count($result->bitmask->value)); 764 $value = array_slice($value, 0, $length); 765 766 for ($i = 0; $i < $length; ++$i) { 767 $value[$i] = $value[$i] & $result->bitmask->value[$i]; 768 } 769 770 $value = static::trim($value); 771 } 772 773 return $result; 774 } 775 776 /** 777 * Compares two numbers. 778 * 779 * @param array $x_value 780 * @param bool $x_negative 781 * @param array $y_value 782 * @param bool $y_negative 783 * @return int 784 * @see static::compare() 785 */ 786 protected static function compareHelper(array $x_value, $x_negative, array $y_value, $y_negative) 787 { 788 if ($x_negative != $y_negative) { 789 return (!$x_negative && $y_negative) ? 1 : -1; 790 } 791 792 $result = $x_negative ? -1 : 1; 793 794 if (count($x_value) != count($y_value)) { 795 return (count($x_value) > count($y_value)) ? $result : -$result; 796 } 797 $size = max(count($x_value), count($y_value)); 798 799 $x_value = array_pad($x_value, $size, 0); 800 $y_value = array_pad($y_value, $size, 0); 801 802 for ($i = count($x_value) - 1; $i >= 0; --$i) { 803 if ($x_value[$i] != $y_value[$i]) { 804 return ($x_value[$i] > $y_value[$i]) ? $result : -$result; 805 } 806 } 807 808 return 0; 809 } 810 811 /** 812 * Absolute value. 813 * 814 * @return PHP 815 */ 816 public function abs() 817 { 818 $temp = new static(); 819 $temp->value = $this->value; 820 821 return $temp; 822 } 823 824 /** 825 * Trim 826 * 827 * Removes leading zeros 828 * 829 * @param list<static> $value 830 * @return list<static> 831 */ 832 protected static function trim(array $value) 833 { 834 for ($i = count($value) - 1; $i >= 0; --$i) { 835 if ($value[$i]) { 836 break; 837 } 838 unset($value[$i]); 839 } 840 841 return $value; 842 } 843 844 /** 845 * Logical Right Shift 846 * 847 * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift. 848 * 849 * @param int $shift 850 * @return PHP 851 */ 852 public function bitwise_rightShift($shift) 853 { 854 $temp = new static(); 855 856 // could just replace lshift with this, but then all lshift() calls would need to be rewritten 857 // and I don't want to do that... 858 $temp->value = $this->value; 859 $temp->rshift($shift); 860 861 return $this->normalize($temp); 862 } 863 864 /** 865 * Logical Left Shift 866 * 867 * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift. 868 * 869 * @param int $shift 870 * @return PHP 871 */ 872 public function bitwise_leftShift($shift) 873 { 874 $temp = new static(); 875 // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten 876 // and I don't want to do that... 877 $temp->value = $this->value; 878 $temp->lshift($shift); 879 880 return $this->normalize($temp); 881 } 882 883 /** 884 * Converts 32-bit integers to bytes. 885 * 886 * @param int $x 887 * @return string 888 */ 889 private static function int2bytes($x) 890 { 891 return ltrim(pack('N', $x), chr(0)); 892 } 893 894 /** 895 * Array Repeat 896 * 897 * @param int $input 898 * @param int $multiplier 899 * @return array 900 */ 901 protected static function array_repeat($input, $multiplier) 902 { 903 return $multiplier ? array_fill(0, $multiplier, $input) : []; 904 } 905 906 /** 907 * Logical Left Shift 908 * 909 * Shifts BigInteger's by $shift bits. 910 * 911 * @param int $shift 912 */ 913 protected function lshift($shift) 914 { 915 if ($shift == 0) { 916 return; 917 } 918 919 $num_digits = (int)($shift / static::BASE); 920 $shift %= static::BASE; 921 $shift = 1 << $shift; 922 923 $carry = 0; 924 925 for ($i = 0; $i < count($this->value); ++$i) { 926 $temp = $this->value[$i] * $shift + $carry; 927 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 928 $this->value[$i] = (int)($temp - $carry * static::BASE_FULL); 929 } 930 931 if ($carry) { 932 $this->value[count($this->value)] = $carry; 933 } 934 935 while ($num_digits--) { 936 array_unshift($this->value, 0); 937 } 938 } 939 940 /** 941 * Logical Right Shift 942 * 943 * Shifts BigInteger's by $shift bits. 944 * 945 * @param int $shift 946 */ 947 protected function rshift($shift) 948 { 949 if ($shift == 0) { 950 return; 951 } 952 953 $num_digits = (int)($shift / static::BASE); 954 $shift %= static::BASE; 955 $carry_shift = static::BASE - $shift; 956 $carry_mask = (1 << $shift) - 1; 957 958 if ($num_digits) { 959 $this->value = array_slice($this->value, $num_digits); 960 } 961 962 $carry = 0; 963 964 for ($i = count($this->value) - 1; $i >= 0; --$i) { 965 $temp = $this->value[$i] >> $shift | $carry; 966 $carry = ($this->value[$i] & $carry_mask) << $carry_shift; 967 $this->value[$i] = $temp; 968 } 969 970 $this->value = static::trim($this->value); 971 } 972 973 /** 974 * Performs modular exponentiation. 975 * 976 * @param PHP $e 977 * @param PHP $n 978 * @return PHP 979 */ 980 protected function powModInner(PHP $e, PHP $n) 981 { 982 try { 983 $class = static::$modexpEngine[static::class]; 984 return $class::powModHelper($this, $e, $n, static::class); 985 } catch (\Exception $err) { 986 return PHP\DefaultEngine::powModHelper($this, $e, $n, static::class); 987 } 988 } 989 990 /** 991 * Performs squaring 992 * 993 * @param list<static> $x 994 * @return list<static> 995 */ 996 protected static function square(array $x) 997 { 998 return count($x) < 2 * self::KARATSUBA_CUTOFF ? 999 self::trim(self::baseSquare($x)) : 1000 self::trim(self::karatsubaSquare($x)); 1001 } 1002 1003 /** 1004 * Performs traditional squaring on two BigIntegers 1005 * 1006 * Squaring can be done faster than multiplying a number by itself can be. See 1007 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} / 1008 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information. 1009 * 1010 * @param array $value 1011 * @return array 1012 */ 1013 protected static function baseSquare(array $value) 1014 { 1015 if (empty($value)) { 1016 return []; 1017 } 1018 $square_value = self::array_repeat(0, 2 * count($value)); 1019 1020 for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) { 1021 $i2 = $i << 1; 1022 1023 $temp = $square_value[$i2] + $value[$i] * $value[$i]; 1024 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 1025 $square_value[$i2] = (int)($temp - static::BASE_FULL * $carry); 1026 1027 // note how we start from $i+1 instead of 0 as we do in multiplication. 1028 for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) { 1029 $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry; 1030 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 1031 $square_value[$k] = (int)($temp - static::BASE_FULL * $carry); 1032 } 1033 1034 // the following line can yield values larger 2**15. at this point, PHP should switch 1035 // over to floats. 1036 $square_value[$i + $max_index + 1] = $carry; 1037 } 1038 1039 return $square_value; 1040 } 1041 1042 /** 1043 * Performs Karatsuba "squaring" on two BigIntegers 1044 * 1045 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and 1046 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}. 1047 * 1048 * @param array $value 1049 * @return array 1050 */ 1051 protected static function karatsubaSquare(array $value) 1052 { 1053 $m = count($value) >> 1; 1054 1055 if ($m < self::KARATSUBA_CUTOFF) { 1056 return self::baseSquare($value); 1057 } 1058 1059 $x1 = array_slice($value, $m); 1060 $x0 = array_slice($value, 0, $m); 1061 1062 $z2 = self::karatsubaSquare($x1); 1063 $z0 = self::karatsubaSquare($x0); 1064 1065 $z1 = self::addHelper($x1, false, $x0, false); 1066 $z1 = self::karatsubaSquare($z1[self::VALUE]); 1067 $temp = self::addHelper($z2, false, $z0, false); 1068 $z1 = self::subtractHelper($z1, false, $temp[self::VALUE], false); 1069 1070 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); 1071 $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]); 1072 1073 $xx = self::addHelper($z2, false, $z1[self::VALUE], $z1[self::SIGN]); 1074 $xx = self::addHelper($xx[self::VALUE], $xx[self::SIGN], $z0, false); 1075 1076 return $xx[self::VALUE]; 1077 } 1078 1079 /** 1080 * Make the current number odd 1081 * 1082 * If the current number is odd it'll be unchanged. If it's even, one will be added to it. 1083 * 1084 * @see self::randomPrime() 1085 */ 1086 protected function make_odd() 1087 { 1088 $this->value[0] |= 1; 1089 } 1090 1091 /** 1092 * Test the number against small primes. 1093 * 1094 * @see self::isPrime() 1095 */ 1096 protected function testSmallPrimes() 1097 { 1098 if ($this->value == [1]) { 1099 return false; 1100 } 1101 if ($this->value == [2]) { 1102 return true; 1103 } 1104 if (~$this->value[0] & 1) { 1105 return false; 1106 } 1107 1108 $value = $this->value; 1109 foreach (static::PRIMES as $prime) { 1110 list(, $r) = self::divide_digit($value, $prime); 1111 if (!$r) { 1112 return count($value) == 1 && $value[0] == $prime; 1113 } 1114 } 1115 1116 return true; 1117 } 1118 1119 /** 1120 * Scan for 1 and right shift by that amount 1121 * 1122 * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s)); 1123 * 1124 * @param PHP $r 1125 * @return int 1126 * @see self::isPrime() 1127 */ 1128 public static function scan1divide(PHP $r) 1129 { 1130 $r_value = &$r->value; 1131 for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) { 1132 $temp = ~$r_value[$i] & static::MAX_DIGIT; 1133 for ($j = 1; ($temp >> $j) & 1; ++$j) { 1134 } 1135 if ($j <= static::BASE) { 1136 break; 1137 } 1138 } 1139 $s = static::BASE * $i + $j; 1140 $r->rshift($s); 1141 return $s; 1142 } 1143 1144 /** 1145 * Performs exponentiation. 1146 * 1147 * @param PHP $n 1148 * @return PHP 1149 */ 1150 protected function powHelper(PHP $n) 1151 { 1152 if ($n->compare(static::$zero[static::class]) == 0) { 1153 return new static(1); 1154 } // n^0 = 1 1155 1156 $temp = clone $this; 1157 while (!$n->equals(static::$one[static::class])) { 1158 $temp = $temp->multiply($this); 1159 $n = $n->subtract(static::$one[static::class]); 1160 } 1161 1162 return $temp; 1163 } 1164 1165 /** 1166 * Is Odd? 1167 * 1168 * @return bool 1169 */ 1170 public function isOdd() 1171 { 1172 return (bool)($this->value[0] & 1); 1173 } 1174 1175 /** 1176 * Tests if a bit is set 1177 * 1178 * @return bool 1179 */ 1180 public function testBit($x) 1181 { 1182 $digit = (int) floor($x / static::BASE); 1183 $bit = $x % static::BASE; 1184 1185 if (!isset($this->value[$digit])) { 1186 return false; 1187 } 1188 1189 return (bool)($this->value[$digit] & (1 << $bit)); 1190 } 1191 1192 /** 1193 * Is Negative? 1194 * 1195 * @return bool 1196 */ 1197 public function isNegative() 1198 { 1199 return $this->is_negative; 1200 } 1201 1202 /** 1203 * Negate 1204 * 1205 * Given $k, returns -$k 1206 * 1207 * @return static 1208 */ 1209 public function negate() 1210 { 1211 $temp = clone $this; 1212 $temp->is_negative = !$temp->is_negative; 1213 1214 return $temp; 1215 } 1216 1217 /** 1218 * Bitwise Split 1219 * 1220 * Splits BigInteger's into chunks of $split bits 1221 * 1222 * @param int $split 1223 * @return list<static> 1224 */ 1225 public function bitwise_split($split) 1226 { 1227 if ($split < 1) { 1228 throw new \RuntimeException('Offset must be greater than 1'); 1229 } 1230 1231 $width = (int)($split / static::BASE); 1232 if (!$width) { 1233 $arr = $this->bitwise_small_split($split); 1234 return array_map(function ($digit) { 1235 $temp = new static(); 1236 $temp->value = $digit != 0 ? [$digit] : []; 1237 return $temp; 1238 }, $arr); 1239 } 1240 1241 $vals = []; 1242 $val = $this->value; 1243 1244 $i = $overflow = 0; 1245 $len = count($val); 1246 while ($i < $len) { 1247 $digit = []; 1248 if (!$overflow) { 1249 $digit = array_slice($val, $i, $width); 1250 $i += $width; 1251 $overflow = $split % static::BASE; 1252 if ($overflow) { 1253 $mask = (1 << $overflow) - 1; 1254 $temp = isset($val[$i]) ? $val[$i] : 0; 1255 $digit[] = $temp & $mask; 1256 } 1257 } else { 1258 $remaining = static::BASE - $overflow; 1259 $tempsplit = $split - $remaining; 1260 $tempwidth = (int)($tempsplit / static::BASE + 1); 1261 $digit = array_slice($val, $i, $tempwidth); 1262 $i += $tempwidth; 1263 $tempoverflow = $tempsplit % static::BASE; 1264 if ($tempoverflow) { 1265 $tempmask = (1 << $tempoverflow) - 1; 1266 $temp = isset($val[$i]) ? $val[$i] : 0; 1267 $digit[] = $temp & $tempmask; 1268 } 1269 $newbits = 0; 1270 for ($j = count($digit) - 1; $j >= 0; $j--) { 1271 $temp = $digit[$j] & $mask; 1272 $digit[$j] = ($digit[$j] >> $overflow) | ($newbits << $remaining); 1273 $newbits = $temp; 1274 } 1275 $overflow = $tempoverflow; 1276 $mask = $tempmask; 1277 } 1278 $temp = new static(); 1279 $temp->value = static::trim($digit); 1280 $vals[] = $temp; 1281 } 1282 1283 return array_reverse($vals); 1284 } 1285 1286 /** 1287 * Bitwise Split where $split < static::BASE 1288 * 1289 * @param int $split 1290 * @return list<int> 1291 */ 1292 private function bitwise_small_split($split) 1293 { 1294 $vals = []; 1295 $val = $this->value; 1296 1297 $mask = (1 << $split) - 1; 1298 1299 $i = $overflow = 0; 1300 $len = count($val); 1301 $val[] = 0; 1302 $remaining = static::BASE; 1303 while ($i != $len) { 1304 $digit = $val[$i] & $mask; 1305 $val[$i] >>= $split; 1306 if (!$overflow) { 1307 $remaining -= $split; 1308 $overflow = $split <= $remaining ? 0 : $split - $remaining; 1309 1310 if (!$remaining) { 1311 $i++; 1312 $remaining = static::BASE; 1313 $overflow = 0; 1314 } 1315 } elseif (++$i != $len) { 1316 $tempmask = (1 << $overflow) - 1; 1317 $digit |= ($val[$i] & $tempmask) << $remaining; 1318 $val[$i] >>= $overflow; 1319 $remaining = static::BASE - $overflow; 1320 $overflow = $split <= $remaining ? 0 : $split - $remaining; 1321 } 1322 1323 $vals[] = $digit; 1324 } 1325 1326 while ($vals[count($vals) - 1] == 0) { 1327 unset($vals[count($vals) - 1]); 1328 } 1329 1330 return array_reverse($vals); 1331 } 1332 1333 /** 1334 * @return bool 1335 */ 1336 protected static function testJITOnWindows() 1337 { 1338 // see https://github.com/php/php-src/issues/11917 1339 if (strtoupper(substr(PHP_OS, 0, 3)) === 'WIN' && function_exists('opcache_get_status') && PHP_VERSION_ID < 80213 && !defined('PHPSECLIB_ALLOW_JIT')) { 1340 $status = opcache_get_status(); 1341 if ($status && isset($status['jit']) && $status['jit']['enabled'] && $status['jit']['on']) { 1342 return true; 1343 } 1344 } 1345 return false; 1346 } 1347 1348 /** 1349 * Return the size of a BigInteger in bits 1350 * 1351 * @return int 1352 */ 1353 public function getLength() 1354 { 1355 $max = count($this->value) - 1; 1356 return $max != -1 ? 1357 $max * static::BASE + intval(ceil(log($this->value[$max] + 1, 2))) : 1358 0; 1359 } 1360} 1361