| [ Index ] |
PHP Cross Reference of DokuWiki |
[Summary view] [Print] [Text view]
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 14 namespace phpseclib3\Math\BigInteger\Engines; 15 16 use phpseclib3\Common\Functions\Strings; 17 use phpseclib3\Exception\BadConfigurationException; 18 19 /** 20 * Pure-PHP Engine. 21 * 22 * @author Jim Wigginton <terrafrost@php.net> 23 */ 24 abstract 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 $remainder->value = [$r]; 537 $quotient->is_negative = $this->is_negative != $y->is_negative; 538 return [$this->normalize($quotient), $this->normalize($remainder)]; 539 } 540 541 $x = clone $this; 542 $y = clone $y; 543 544 $x_sign = $x->is_negative; 545 $y_sign = $y->is_negative; 546 547 $x->is_negative = $y->is_negative = false; 548 549 $diff = $x->compare($y); 550 551 if (!$diff) { 552 $temp = new static(); 553 $temp->value = [1]; 554 $temp->is_negative = $x_sign != $y_sign; 555 return [$this->normalize($temp), $this->normalize(static::$zero[static::class])]; 556 } 557 558 if ($diff < 0) { 559 // if $x is negative, "add" $y. 560 if ($x_sign) { 561 $x = $y->subtract($x); 562 } 563 return [$this->normalize(static::$zero[static::class]), $this->normalize($x)]; 564 } 565 566 // normalize $x and $y as described in HAC 14.23 / 14.24 567 $msb = $y->value[count($y->value) - 1]; 568 for ($shift = 0; !($msb & static::MSB); ++$shift) { 569 $msb <<= 1; 570 } 571 $x->lshift($shift); 572 $y->lshift($shift); 573 $y_value = &$y->value; 574 575 $x_max = count($x->value) - 1; 576 $y_max = count($y->value) - 1; 577 578 $quotient = new static(); 579 $quotient_value = &$quotient->value; 580 $quotient_value = self::array_repeat(0, $x_max - $y_max + 1); 581 582 static $temp, $lhs, $rhs; 583 if (!isset($temp)) { 584 $temp = new static(); 585 $lhs = new static(); 586 $rhs = new static(); 587 } 588 if (static::class != get_class($temp)) { 589 $temp = new static(); 590 $lhs = new static(); 591 $rhs = new static(); 592 } 593 $temp_value = &$temp->value; 594 $rhs_value = &$rhs->value; 595 596 // $temp = $y << ($x_max - $y_max-1) in base 2**26 597 $temp_value = array_merge(self::array_repeat(0, $x_max - $y_max), $y_value); 598 599 while ($x->compare($temp) >= 0) { 600 // calculate the "common residue" 601 ++$quotient_value[$x_max - $y_max]; 602 $x = $x->subtract($temp); 603 $x_max = count($x->value) - 1; 604 } 605 606 for ($i = $x_max; $i >= $y_max + 1; --$i) { 607 $x_value = &$x->value; 608 $x_window = [ 609 isset($x_value[$i]) ? $x_value[$i] : 0, 610 isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0, 611 isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0 612 ]; 613 $y_window = [ 614 $y_value[$y_max], 615 ($y_max > 0) ? $y_value[$y_max - 1] : 0 616 ]; 617 618 $q_index = $i - $y_max - 1; 619 if ($x_window[0] == $y_window[0]) { 620 $quotient_value[$q_index] = static::MAX_DIGIT; 621 } else { 622 $quotient_value[$q_index] = self::safe_divide( 623 $x_window[0] * static::BASE_FULL + $x_window[1], 624 $y_window[0] 625 ); 626 } 627 628 $temp_value = [$y_window[1], $y_window[0]]; 629 630 $lhs->value = [$quotient_value[$q_index]]; 631 $lhs = $lhs->multiply($temp); 632 633 $rhs_value = [$x_window[2], $x_window[1], $x_window[0]]; 634 635 while ($lhs->compare($rhs) > 0) { 636 --$quotient_value[$q_index]; 637 638 $lhs->value = [$quotient_value[$q_index]]; 639 $lhs = $lhs->multiply($temp); 640 } 641 642 $adjust = self::array_repeat(0, $q_index); 643 $temp_value = [$quotient_value[$q_index]]; 644 $temp = $temp->multiply($y); 645 $temp_value = &$temp->value; 646 if (count($temp_value)) { 647 $temp_value = array_merge($adjust, $temp_value); 648 } 649 650 $x = $x->subtract($temp); 651 652 if ($x->compare(static::$zero[static::class]) < 0) { 653 $temp_value = array_merge($adjust, $y_value); 654 $x = $x->add($temp); 655 656 --$quotient_value[$q_index]; 657 } 658 659 $x_max = count($x_value) - 1; 660 } 661 662 // unnormalize the remainder 663 $x->rshift($shift); 664 665 $quotient->is_negative = $x_sign != $y_sign; 666 667 // calculate the "common residue", if appropriate 668 if ($x_sign) { 669 $y->rshift($shift); 670 $x = $y->subtract($x); 671 } 672 673 return [$this->normalize($quotient), $this->normalize($x)]; 674 } 675 676 /** 677 * Divides a BigInteger by a regular integer 678 * 679 * abc / x = a00 / x + b0 / x + c / x 680 * 681 * @param array $dividend 682 * @param int $divisor 683 * @return array 684 */ 685 private static function divide_digit(array $dividend, $divisor) 686 { 687 $carry = 0; 688 $result = []; 689 690 for ($i = count($dividend) - 1; $i >= 0; --$i) { 691 $temp = static::BASE_FULL * $carry + $dividend[$i]; 692 $result[$i] = self::safe_divide($temp, $divisor); 693 $carry = (int)($temp - $divisor * $result[$i]); 694 } 695 696 return [$result, $carry]; 697 } 698 699 /** 700 * Single digit division 701 * 702 * Even if int64 is being used the division operator will return a float64 value 703 * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't 704 * have the precision of int64 this is a problem so, when int64 is being used, 705 * we'll guarantee that the dividend is divisible by first subtracting the remainder. 706 * 707 * @param int $x 708 * @param int $y 709 * @return int 710 */ 711 private static function safe_divide($x, $y) 712 { 713 if (static::BASE === 26) { 714 return (int)($x / $y); 715 } 716 717 // static::BASE === 31 718 /** @var int */ 719 return ($x - ($x % $y)) / $y; 720 } 721 722 /** 723 * Convert an array / boolean to a PHP BigInteger object 724 * 725 * @param array $arr 726 * @return static 727 */ 728 protected function convertToObj(array $arr) 729 { 730 $result = new static(); 731 $result->value = $arr[self::VALUE]; 732 $result->is_negative = $arr[self::SIGN]; 733 734 return $this->normalize($result); 735 } 736 737 /** 738 * Normalize 739 * 740 * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision 741 * 742 * @param PHP $result 743 * @return static 744 */ 745 protected function normalize(PHP $result) 746 { 747 $result->precision = $this->precision; 748 $result->bitmask = $this->bitmask; 749 750 $value = &$result->value; 751 752 if (!count($value)) { 753 $result->is_negative = false; 754 return $result; 755 } 756 757 $value = static::trim($value); 758 759 if (!empty($result->bitmask->value)) { 760 $length = min(count($value), count($result->bitmask->value)); 761 $value = array_slice($value, 0, $length); 762 763 for ($i = 0; $i < $length; ++$i) { 764 $value[$i] = $value[$i] & $result->bitmask->value[$i]; 765 } 766 767 $value = static::trim($value); 768 } 769 770 return $result; 771 } 772 773 /** 774 * Compares two numbers. 775 * 776 * @param array $x_value 777 * @param bool $x_negative 778 * @param array $y_value 779 * @param bool $y_negative 780 * @return int 781 * @see static::compare() 782 */ 783 protected static function compareHelper(array $x_value, $x_negative, array $y_value, $y_negative) 784 { 785 if ($x_negative != $y_negative) { 786 return (!$x_negative && $y_negative) ? 1 : -1; 787 } 788 789 $result = $x_negative ? -1 : 1; 790 791 if (count($x_value) != count($y_value)) { 792 return (count($x_value) > count($y_value)) ? $result : -$result; 793 } 794 $size = max(count($x_value), count($y_value)); 795 796 $x_value = array_pad($x_value, $size, 0); 797 $y_value = array_pad($y_value, $size, 0); 798 799 for ($i = count($x_value) - 1; $i >= 0; --$i) { 800 if ($x_value[$i] != $y_value[$i]) { 801 return ($x_value[$i] > $y_value[$i]) ? $result : -$result; 802 } 803 } 804 805 return 0; 806 } 807 808 /** 809 * Absolute value. 810 * 811 * @return PHP 812 */ 813 public function abs() 814 { 815 $temp = new static(); 816 $temp->value = $this->value; 817 818 return $temp; 819 } 820 821 /** 822 * Trim 823 * 824 * Removes leading zeros 825 * 826 * @param list<static> $value 827 * @return list<static> 828 */ 829 protected static function trim(array $value) 830 { 831 for ($i = count($value) - 1; $i >= 0; --$i) { 832 if ($value[$i]) { 833 break; 834 } 835 unset($value[$i]); 836 } 837 838 return $value; 839 } 840 841 /** 842 * Logical Right Shift 843 * 844 * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift. 845 * 846 * @param int $shift 847 * @return PHP 848 */ 849 public function bitwise_rightShift($shift) 850 { 851 $temp = new static(); 852 853 // could just replace lshift with this, but then all lshift() calls would need to be rewritten 854 // and I don't want to do that... 855 $temp->value = $this->value; 856 $temp->rshift($shift); 857 858 return $this->normalize($temp); 859 } 860 861 /** 862 * Logical Left Shift 863 * 864 * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift. 865 * 866 * @param int $shift 867 * @return PHP 868 */ 869 public function bitwise_leftShift($shift) 870 { 871 $temp = new static(); 872 // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten 873 // and I don't want to do that... 874 $temp->value = $this->value; 875 $temp->lshift($shift); 876 877 return $this->normalize($temp); 878 } 879 880 /** 881 * Converts 32-bit integers to bytes. 882 * 883 * @param int $x 884 * @return string 885 */ 886 private static function int2bytes($x) 887 { 888 return ltrim(pack('N', $x), chr(0)); 889 } 890 891 /** 892 * Array Repeat 893 * 894 * @param int $input 895 * @param int $multiplier 896 * @return array 897 */ 898 protected static function array_repeat($input, $multiplier) 899 { 900 return $multiplier ? array_fill(0, $multiplier, $input) : []; 901 } 902 903 /** 904 * Logical Left Shift 905 * 906 * Shifts BigInteger's by $shift bits. 907 * 908 * @param int $shift 909 */ 910 protected function lshift($shift) 911 { 912 if ($shift == 0) { 913 return; 914 } 915 916 $num_digits = (int)($shift / static::BASE); 917 $shift %= static::BASE; 918 $shift = 1 << $shift; 919 920 $carry = 0; 921 922 for ($i = 0; $i < count($this->value); ++$i) { 923 $temp = $this->value[$i] * $shift + $carry; 924 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 925 $this->value[$i] = (int)($temp - $carry * static::BASE_FULL); 926 } 927 928 if ($carry) { 929 $this->value[count($this->value)] = $carry; 930 } 931 932 while ($num_digits--) { 933 array_unshift($this->value, 0); 934 } 935 } 936 937 /** 938 * Logical Right Shift 939 * 940 * Shifts BigInteger's by $shift bits. 941 * 942 * @param int $shift 943 */ 944 protected function rshift($shift) 945 { 946 if ($shift == 0) { 947 return; 948 } 949 950 $num_digits = (int)($shift / static::BASE); 951 $shift %= static::BASE; 952 $carry_shift = static::BASE - $shift; 953 $carry_mask = (1 << $shift) - 1; 954 955 if ($num_digits) { 956 $this->value = array_slice($this->value, $num_digits); 957 } 958 959 $carry = 0; 960 961 for ($i = count($this->value) - 1; $i >= 0; --$i) { 962 $temp = $this->value[$i] >> $shift | $carry; 963 $carry = ($this->value[$i] & $carry_mask) << $carry_shift; 964 $this->value[$i] = $temp; 965 } 966 967 $this->value = static::trim($this->value); 968 } 969 970 /** 971 * Performs modular exponentiation. 972 * 973 * @param PHP $e 974 * @param PHP $n 975 * @return PHP 976 */ 977 protected function powModInner(PHP $e, PHP $n) 978 { 979 try { 980 $class = static::$modexpEngine[static::class]; 981 return $class::powModHelper($this, $e, $n, static::class); 982 } catch (\Exception $err) { 983 return PHP\DefaultEngine::powModHelper($this, $e, $n, static::class); 984 } 985 } 986 987 /** 988 * Performs squaring 989 * 990 * @param list<static> $x 991 * @return list<static> 992 */ 993 protected static function square(array $x) 994 { 995 return count($x) < 2 * self::KARATSUBA_CUTOFF ? 996 self::trim(self::baseSquare($x)) : 997 self::trim(self::karatsubaSquare($x)); 998 } 999 1000 /** 1001 * Performs traditional squaring on two BigIntegers 1002 * 1003 * Squaring can be done faster than multiplying a number by itself can be. See 1004 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} / 1005 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information. 1006 * 1007 * @param array $value 1008 * @return array 1009 */ 1010 protected static function baseSquare(array $value) 1011 { 1012 if (empty($value)) { 1013 return []; 1014 } 1015 $square_value = self::array_repeat(0, 2 * count($value)); 1016 1017 for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) { 1018 $i2 = $i << 1; 1019 1020 $temp = $square_value[$i2] + $value[$i] * $value[$i]; 1021 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 1022 $square_value[$i2] = (int)($temp - static::BASE_FULL * $carry); 1023 1024 // note how we start from $i+1 instead of 0 as we do in multiplication. 1025 for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) { 1026 $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry; 1027 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 1028 $square_value[$k] = (int)($temp - static::BASE_FULL * $carry); 1029 } 1030 1031 // the following line can yield values larger 2**15. at this point, PHP should switch 1032 // over to floats. 1033 $square_value[$i + $max_index + 1] = $carry; 1034 } 1035 1036 return $square_value; 1037 } 1038 1039 /** 1040 * Performs Karatsuba "squaring" on two BigIntegers 1041 * 1042 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and 1043 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}. 1044 * 1045 * @param array $value 1046 * @return array 1047 */ 1048 protected static function karatsubaSquare(array $value) 1049 { 1050 $m = count($value) >> 1; 1051 1052 if ($m < self::KARATSUBA_CUTOFF) { 1053 return self::baseSquare($value); 1054 } 1055 1056 $x1 = array_slice($value, $m); 1057 $x0 = array_slice($value, 0, $m); 1058 1059 $z2 = self::karatsubaSquare($x1); 1060 $z0 = self::karatsubaSquare($x0); 1061 1062 $z1 = self::addHelper($x1, false, $x0, false); 1063 $z1 = self::karatsubaSquare($z1[self::VALUE]); 1064 $temp = self::addHelper($z2, false, $z0, false); 1065 $z1 = self::subtractHelper($z1, false, $temp[self::VALUE], false); 1066 1067 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); 1068 $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]); 1069 1070 $xx = self::addHelper($z2, false, $z1[self::VALUE], $z1[self::SIGN]); 1071 $xx = self::addHelper($xx[self::VALUE], $xx[self::SIGN], $z0, false); 1072 1073 return $xx[self::VALUE]; 1074 } 1075 1076 /** 1077 * Make the current number odd 1078 * 1079 * If the current number is odd it'll be unchanged. If it's even, one will be added to it. 1080 * 1081 * @see self::randomPrime() 1082 */ 1083 protected function make_odd() 1084 { 1085 $this->value[0] |= 1; 1086 } 1087 1088 /** 1089 * Test the number against small primes. 1090 * 1091 * @see self::isPrime() 1092 */ 1093 protected function testSmallPrimes() 1094 { 1095 if ($this->value == [1]) { 1096 return false; 1097 } 1098 if ($this->value == [2]) { 1099 return true; 1100 } 1101 if (~$this->value[0] & 1) { 1102 return false; 1103 } 1104 1105 $value = $this->value; 1106 foreach (static::PRIMES as $prime) { 1107 list(, $r) = self::divide_digit($value, $prime); 1108 if (!$r) { 1109 return count($value) == 1 && $value[0] == $prime; 1110 } 1111 } 1112 1113 return true; 1114 } 1115 1116 /** 1117 * Scan for 1 and right shift by that amount 1118 * 1119 * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s)); 1120 * 1121 * @param PHP $r 1122 * @return int 1123 * @see self::isPrime() 1124 */ 1125 public static function scan1divide(PHP $r) 1126 { 1127 $r_value = &$r->value; 1128 for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) { 1129 $temp = ~$r_value[$i] & static::MAX_DIGIT; 1130 for ($j = 1; ($temp >> $j) & 1; ++$j) { 1131 } 1132 if ($j <= static::BASE) { 1133 break; 1134 } 1135 } 1136 $s = static::BASE * $i + $j; 1137 $r->rshift($s); 1138 return $s; 1139 } 1140 1141 /** 1142 * Performs exponentiation. 1143 * 1144 * @param PHP $n 1145 * @return PHP 1146 */ 1147 protected function powHelper(PHP $n) 1148 { 1149 if ($n->compare(static::$zero[static::class]) == 0) { 1150 return new static(1); 1151 } // n^0 = 1 1152 1153 $temp = clone $this; 1154 while (!$n->equals(static::$one[static::class])) { 1155 $temp = $temp->multiply($this); 1156 $n = $n->subtract(static::$one[static::class]); 1157 } 1158 1159 return $temp; 1160 } 1161 1162 /** 1163 * Is Odd? 1164 * 1165 * @return bool 1166 */ 1167 public function isOdd() 1168 { 1169 return (bool)($this->value[0] & 1); 1170 } 1171 1172 /** 1173 * Tests if a bit is set 1174 * 1175 * @return bool 1176 */ 1177 public function testBit($x) 1178 { 1179 $digit = (int) floor($x / static::BASE); 1180 $bit = $x % static::BASE; 1181 1182 if (!isset($this->value[$digit])) { 1183 return false; 1184 } 1185 1186 return (bool)($this->value[$digit] & (1 << $bit)); 1187 } 1188 1189 /** 1190 * Is Negative? 1191 * 1192 * @return bool 1193 */ 1194 public function isNegative() 1195 { 1196 return $this->is_negative; 1197 } 1198 1199 /** 1200 * Negate 1201 * 1202 * Given $k, returns -$k 1203 * 1204 * @return static 1205 */ 1206 public function negate() 1207 { 1208 $temp = clone $this; 1209 $temp->is_negative = !$temp->is_negative; 1210 1211 return $temp; 1212 } 1213 1214 /** 1215 * Bitwise Split 1216 * 1217 * Splits BigInteger's into chunks of $split bits 1218 * 1219 * @param int $split 1220 * @return list<static> 1221 */ 1222 public function bitwise_split($split) 1223 { 1224 if ($split < 1) { 1225 throw new \RuntimeException('Offset must be greater than 1'); 1226 } 1227 1228 $width = (int)($split / static::BASE); 1229 if (!$width) { 1230 $arr = $this->bitwise_small_split($split); 1231 return array_map(function ($digit) { 1232 $temp = new static(); 1233 $temp->value = $digit != 0 ? [$digit] : []; 1234 return $temp; 1235 }, $arr); 1236 } 1237 1238 $vals = []; 1239 $val = $this->value; 1240 1241 $i = $overflow = 0; 1242 $len = count($val); 1243 while ($i < $len) { 1244 $digit = []; 1245 if (!$overflow) { 1246 $digit = array_slice($val, $i, $width); 1247 $i += $width; 1248 $overflow = $split % static::BASE; 1249 if ($overflow) { 1250 $mask = (1 << $overflow) - 1; 1251 $temp = isset($val[$i]) ? $val[$i] : 0; 1252 $digit[] = $temp & $mask; 1253 } 1254 } else { 1255 $remaining = static::BASE - $overflow; 1256 $tempsplit = $split - $remaining; 1257 $tempwidth = (int)($tempsplit / static::BASE + 1); 1258 $digit = array_slice($val, $i, $tempwidth); 1259 $i += $tempwidth; 1260 $tempoverflow = $tempsplit % static::BASE; 1261 if ($tempoverflow) { 1262 $tempmask = (1 << $tempoverflow) - 1; 1263 $temp = isset($val[$i]) ? $val[$i] : 0; 1264 $digit[] = $temp & $tempmask; 1265 } 1266 $newbits = 0; 1267 for ($j = count($digit) - 1; $j >= 0; $j--) { 1268 $temp = $digit[$j] & $mask; 1269 $digit[$j] = ($digit[$j] >> $overflow) | ($newbits << $remaining); 1270 $newbits = $temp; 1271 } 1272 $overflow = $tempoverflow; 1273 $mask = $tempmask; 1274 } 1275 $temp = new static(); 1276 $temp->value = static::trim($digit); 1277 $vals[] = $temp; 1278 } 1279 1280 return array_reverse($vals); 1281 } 1282 1283 /** 1284 * Bitwise Split where $split < static::BASE 1285 * 1286 * @param int $split 1287 * @return list<int> 1288 */ 1289 private function bitwise_small_split($split) 1290 { 1291 $vals = []; 1292 $val = $this->value; 1293 1294 $mask = (1 << $split) - 1; 1295 1296 $i = $overflow = 0; 1297 $len = count($val); 1298 $val[] = 0; 1299 $remaining = static::BASE; 1300 while ($i != $len) { 1301 $digit = $val[$i] & $mask; 1302 $val[$i] >>= $split; 1303 if (!$overflow) { 1304 $remaining -= $split; 1305 $overflow = $split <= $remaining ? 0 : $split - $remaining; 1306 1307 if (!$remaining) { 1308 $i++; 1309 $remaining = static::BASE; 1310 $overflow = 0; 1311 } 1312 } elseif (++$i != $len) { 1313 $tempmask = (1 << $overflow) - 1; 1314 $digit |= ($val[$i] & $tempmask) << $remaining; 1315 $val[$i] >>= $overflow; 1316 $remaining = static::BASE - $overflow; 1317 $overflow = $split <= $remaining ? 0 : $split - $remaining; 1318 } 1319 1320 $vals[] = $digit; 1321 } 1322 1323 while ($vals[count($vals) - 1] == 0) { 1324 unset($vals[count($vals) - 1]); 1325 } 1326 1327 return array_reverse($vals); 1328 } 1329 1330 /** 1331 * @return bool 1332 */ 1333 protected static function testJITOnWindows() 1334 { 1335 // see https://github.com/php/php-src/issues/11917 1336 if (strtoupper(substr(PHP_OS, 0, 3)) === 'WIN' && function_exists('opcache_get_status') && PHP_VERSION_ID < 80213 && !defined('PHPSECLIB_ALLOW_JIT')) { 1337 $status = opcache_get_status(); 1338 if ($status && isset($status['jit']) && $status['jit']['enabled'] && $status['jit']['on']) { 1339 return true; 1340 } 1341 } 1342 return false; 1343 } 1344 1345 /** 1346 * Return the size of a BigInteger in bits 1347 * 1348 * @return int 1349 */ 1350 public function getLength() 1351 { 1352 $max = count($this->value) - 1; 1353 return $max != -1 ? 1354 $max * static::BASE + intval(ceil(log($this->value[$max] + 1, 2))) : 1355 0; 1356 } 1357 }
title
Description
Body
title
Description
Body
title
Description
Body
title
Body