[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * Pure-PHP 64-bit 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  /**
  17   * Pure-PHP 64-bit Engine.
  18   *
  19   * Uses 64-bit integers if int size is 8 bits
  20   *
  21   * @author  Jim Wigginton <terrafrost@php.net>
  22   */
  23  class PHP64 extends PHP
  24  {
  25      // Constants used by PHP.php
  26      const BASE = 31;
  27      const BASE_FULL = 0x80000000;
  28      const MAX_DIGIT = 0x7FFFFFFF;
  29      const MSB = 0x40000000;
  30  
  31      /**
  32       * MAX10 in greatest MAX10LEN satisfying
  33       * MAX10 = 10**MAX10LEN <= 2**BASE.
  34       */
  35      const MAX10 = 1000000000;
  36  
  37      /**
  38       * MAX10LEN in greatest MAX10LEN satisfying
  39       * MAX10 = 10**MAX10LEN <= 2**BASE.
  40       */
  41      const MAX10LEN = 9;
  42      const MAX_DIGIT2 = 4611686018427387904;
  43  
  44      /**
  45       * Initialize a PHP64 BigInteger Engine instance
  46       *
  47       * @param int $base
  48       * @see parent::initialize()
  49       */
  50      protected function initialize($base)
  51      {
  52          if ($base != 256 && $base != -256) {
  53              return parent::initialize($base);
  54          }
  55  
  56          $val = $this->value;
  57          $this->value = [];
  58          $vals = &$this->value;
  59          $i = strlen($val);
  60          if (!$i) {
  61              return;
  62          }
  63  
  64          while (true) {
  65              $i -= 4;
  66              if ($i < 0) {
  67                  if ($i == -4) {
  68                      break;
  69                  }
  70                  $val = substr($val, 0, 4 + $i);
  71                  $val = str_pad($val, 4, "\0", STR_PAD_LEFT);
  72                  if ($val == "\0\0\0\0") {
  73                      break;
  74                  }
  75                  $i = 0;
  76              }
  77              list(, $digit) = unpack('N', substr($val, $i, 4));
  78              $step = count($vals) & 7;
  79              if (!$step) {
  80                  $digit &= static::MAX_DIGIT;
  81                  $i++;
  82              } else {
  83                  $shift = 8 - $step;
  84                  $digit >>= $shift;
  85                  $shift = 32 - $shift;
  86                  $digit &= (1 << $shift) - 1;
  87                  $temp = $i > 0 ? ord($val[$i - 1]) : 0;
  88                  $digit |= ($temp << $shift) & 0x7F000000;
  89              }
  90              $vals[] = $digit;
  91          }
  92          while (end($vals) === 0) {
  93              array_pop($vals);
  94          }
  95          reset($vals);
  96      }
  97  
  98      /**
  99       * Test for engine validity
 100       *
 101       * @see parent::__construct()
 102       * @return bool
 103       */
 104      public static function isValidEngine()
 105      {
 106          return PHP_INT_SIZE >= 8 && !self::testJITOnWindows();
 107      }
 108  
 109      /**
 110       * Adds two BigIntegers.
 111       *
 112       * @param PHP64 $y
 113       * @return PHP64
 114       */
 115      public function add(PHP64 $y)
 116      {
 117          $temp = self::addHelper($this->value, $this->is_negative, $y->value, $y->is_negative);
 118  
 119          return $this->convertToObj($temp);
 120      }
 121  
 122      /**
 123       * Subtracts two BigIntegers.
 124       *
 125       * @param PHP64 $y
 126       * @return PHP64
 127       */
 128      public function subtract(PHP64 $y)
 129      {
 130          $temp = self::subtractHelper($this->value, $this->is_negative, $y->value, $y->is_negative);
 131  
 132          return $this->convertToObj($temp);
 133      }
 134  
 135      /**
 136       * Multiplies two BigIntegers.
 137       *
 138       * @param PHP64 $y
 139       * @return PHP64
 140       */
 141      public function multiply(PHP64 $y)
 142      {
 143          $temp = self::multiplyHelper($this->value, $this->is_negative, $y->value, $y->is_negative);
 144  
 145          return $this->convertToObj($temp);
 146      }
 147  
 148      /**
 149       * Divides two BigIntegers.
 150       *
 151       * Returns an array whose first element contains the quotient and whose second element contains the
 152       * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
 153       * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
 154       * and the divisor (basically, the "common residue" is the first positive modulo).
 155       *
 156       * @param PHP64 $y
 157       * @return array{PHP64, PHP64}
 158       */
 159      public function divide(PHP64 $y)
 160      {
 161          return $this->divideHelper($y);
 162      }
 163  
 164      /**
 165       * Calculates modular inverses.
 166       *
 167       * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
 168       * @param PHP64 $n
 169       * @return false|PHP64
 170       */
 171      public function modInverse(PHP64 $n)
 172      {
 173          return $this->modInverseHelper($n);
 174      }
 175  
 176      /**
 177       * Calculates modular inverses.
 178       *
 179       * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
 180       * @param PHP64 $n
 181       * @return PHP64[]
 182       */
 183      public function extendedGCD(PHP64 $n)
 184      {
 185          return $this->extendedGCDHelper($n);
 186      }
 187  
 188      /**
 189       * Calculates the greatest common divisor
 190       *
 191       * Say you have 693 and 609.  The GCD is 21.
 192       *
 193       * @param PHP64 $n
 194       * @return PHP64
 195       */
 196      public function gcd(PHP64 $n)
 197      {
 198          return $this->extendedGCD($n)['gcd'];
 199      }
 200  
 201      /**
 202       * Logical And
 203       *
 204       * @param PHP64 $x
 205       * @return PHP64
 206       */
 207      public function bitwise_and(PHP64 $x)
 208      {
 209          return $this->bitwiseAndHelper($x);
 210      }
 211  
 212      /**
 213       * Logical Or
 214       *
 215       * @param PHP64 $x
 216       * @return PHP64
 217       */
 218      public function bitwise_or(PHP64 $x)
 219      {
 220          return $this->bitwiseOrHelper($x);
 221      }
 222  
 223      /**
 224       * Logical Exclusive Or
 225       *
 226       * @param PHP64 $x
 227       * @return PHP64
 228       */
 229      public function bitwise_xor(PHP64 $x)
 230      {
 231          return $this->bitwiseXorHelper($x);
 232      }
 233  
 234      /**
 235       * Compares two numbers.
 236       *
 237       * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite.  The reason for this is
 238       * demonstrated thusly:
 239       *
 240       * $x  > $y: $x->compare($y)  > 0
 241       * $x  < $y: $x->compare($y)  < 0
 242       * $x == $y: $x->compare($y) == 0
 243       *
 244       * Note how the same comparison operator is used.  If you want to test for equality, use $x->equals($y).
 245       *
 246       * {@internal Could return $this->subtract($x), but that's not as fast as what we do do.}
 247       *
 248       * @param PHP64 $y
 249       * @return int in case < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
 250       * @see self::equals()
 251       */
 252      public function compare(PHP64 $y)
 253      {
 254          return parent::compareHelper($this->value, $this->is_negative, $y->value, $y->is_negative);
 255      }
 256  
 257      /**
 258       * Tests the equality of two numbers.
 259       *
 260       * If you need to see if one number is greater than or less than another number, use BigInteger::compare()
 261       *
 262       * @param PHP64 $x
 263       * @return bool
 264       */
 265      public function equals(PHP64 $x)
 266      {
 267          return $this->value === $x->value && $this->is_negative == $x->is_negative;
 268      }
 269  
 270      /**
 271       * Performs modular exponentiation.
 272       *
 273       * @param PHP64 $e
 274       * @param PHP64 $n
 275       * @return PHP64
 276       */
 277      public function modPow(PHP64 $e, PHP64 $n)
 278      {
 279          return $this->powModOuter($e, $n);
 280      }
 281  
 282      /**
 283       * Performs modular exponentiation.
 284       *
 285       * Alias for modPow().
 286       *
 287       * @param PHP64 $e
 288       * @param PHP64 $n
 289       * @return PHP64|false
 290       */
 291      public function powMod(PHP64 $e, PHP64 $n)
 292      {
 293          return $this->powModOuter($e, $n);
 294      }
 295  
 296      /**
 297       * Generate a random prime number between a range
 298       *
 299       * If there's not a prime within the given range, false will be returned.
 300       *
 301       * @param PHP64 $min
 302       * @param PHP64 $max
 303       * @return false|PHP64
 304       */
 305      public static function randomRangePrime(PHP64 $min, PHP64 $max)
 306      {
 307          return self::randomRangePrimeOuter($min, $max);
 308      }
 309  
 310      /**
 311       * Generate a random number between a range
 312       *
 313       * Returns a random number between $min and $max where $min and $max
 314       * can be defined using one of the two methods:
 315       *
 316       * BigInteger::randomRange($min, $max)
 317       * BigInteger::randomRange($max, $min)
 318       *
 319       * @param PHP64 $min
 320       * @param PHP64 $max
 321       * @return PHP64
 322       */
 323      public static function randomRange(PHP64 $min, PHP64 $max)
 324      {
 325          return self::randomRangeHelper($min, $max);
 326      }
 327  
 328      /**
 329       * Performs exponentiation.
 330       *
 331       * @param PHP64 $n
 332       * @return PHP64
 333       */
 334      public function pow(PHP64 $n)
 335      {
 336          return $this->powHelper($n);
 337      }
 338  
 339      /**
 340       * Return the minimum BigInteger between an arbitrary number of BigIntegers.
 341       *
 342       * @param PHP64 ...$nums
 343       * @return PHP64
 344       */
 345      public static function min(PHP64 ...$nums)
 346      {
 347          return self::minHelper($nums);
 348      }
 349  
 350      /**
 351       * Return the maximum BigInteger between an arbitrary number of BigIntegers.
 352       *
 353       * @param PHP64 ...$nums
 354       * @return PHP64
 355       */
 356      public static function max(PHP64 ...$nums)
 357      {
 358          return self::maxHelper($nums);
 359      }
 360  
 361      /**
 362       * Tests BigInteger to see if it is between two integers, inclusive
 363       *
 364       * @param PHP64 $min
 365       * @param PHP64 $max
 366       * @return bool
 367       */
 368      public function between(PHP64 $min, PHP64 $max)
 369      {
 370          return $this->compare($min) >= 0 && $this->compare($max) <= 0;
 371      }
 372  }