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