[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * Pure-PHP 32-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 32-bit Engine.
  20   *
  21   * Uses 64-bit floats if int size is 4 bits
  22   *
  23   * @package PHP32
  24   * @author  Jim Wigginton <[email protected]>
  25   * @access  public
  26   */
  27  class PHP32 extends PHP
  28  {
  29      // Constants used by PHP.php
  30      const BASE = 26;
  31      const BASE_FULL = 0x4000000;
  32      const MAX_DIGIT = 0x3FFFFFF;
  33      const MSB = 0x2000000;
  34  
  35      /**
  36       * MAX10 in greatest MAX10LEN satisfying
  37       * MAX10 = 10**MAX10LEN <= 2**BASE.
  38       */
  39      const MAX10 = 10000000;
  40  
  41      /**
  42       * MAX10LEN in greatest MAX10LEN satisfying
  43       * MAX10 = 10**MAX10LEN <= 2**BASE.
  44       */
  45      const MAX10LEN = 7;
  46      const MAX_DIGIT2 = 4503599627370496;
  47  
  48      /**
  49       * Initialize a PHP32 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) & 3;
  83              if ($step) {
  84                  $digit >>= 2 * $step;
  85              }
  86              if ($step != 3) {
  87                  $digit &= static::MAX_DIGIT;
  88                  $i++;
  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 >= 4;
 107      }
 108  
 109      /**
 110       * Adds two BigIntegers.
 111       *
 112       * @param PHP32 $y
 113       * @return PHP32
 114       */
 115      public function add(PHP32 $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 PHP32 $y
 126       * @return PHP32
 127       */
 128      public function subtract(PHP32 $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 PHP32 $y
 139       * @return PHP32
 140       */
 141      public function multiply(PHP32 $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 PHP32 $y
 157       * @return array{PHP32, PHP32}
 158       */
 159      public function divide(PHP32 $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 PHP32 $n
 169       * @return false|PHP32
 170       */
 171      public function modInverse(PHP32 $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 PHP32 $n
 181       * @return PHP32[]
 182       */
 183      public function extendedGCD(PHP32 $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 PHP32 $n
 194       * @return PHP32
 195       */
 196      public function gcd(PHP32 $n)
 197      {
 198          return $this->extendedGCD($n)['gcd'];
 199      }
 200  
 201      /**
 202       * Logical And
 203       *
 204       * @param PHP32 $x
 205       * @return PHP32
 206       */
 207      public function bitwise_and(PHP32 $x)
 208      {
 209          return $this->bitwiseAndHelper($x);
 210      }
 211  
 212      /**
 213       * Logical Or
 214       *
 215       * @param PHP32 $x
 216       * @return PHP32
 217       */
 218      public function bitwise_or(PHP32 $x)
 219      {
 220          return $this->bitwiseOrHelper($x);
 221      }
 222  
 223      /**
 224       * Logical Exclusive Or
 225       *
 226       * @param PHP32 $x
 227       * @return PHP32
 228       */
 229      public function bitwise_xor(PHP32 $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 PHP32 $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       * @access public
 251       * @see self::equals()
 252       */
 253      public function compare(PHP32 $y)
 254      {
 255          return $this->compareHelper($this->value, $this->is_negative, $y->value, $y->is_negative);
 256      }
 257  
 258      /**
 259       * Tests the equality of two numbers.
 260       *
 261       * If you need to see if one number is greater than or less than another number, use BigInteger::compare()
 262       *
 263       * @param PHP32 $x
 264       * @return bool
 265       */
 266      public function equals(PHP32 $x)
 267      {
 268          return $this->value === $x->value && $this->is_negative == $x->is_negative;
 269      }
 270  
 271      /**
 272       * Performs modular exponentiation.
 273       *
 274       * @param PHP32 $e
 275       * @param PHP32 $n
 276       * @return PHP32
 277       */
 278      public function modPow(PHP32 $e, PHP32 $n)
 279      {
 280          return $this->powModOuter($e, $n);
 281      }
 282  
 283      /**
 284       * Performs modular exponentiation.
 285       *
 286       * Alias for modPow().
 287       *
 288       * @param PHP32 $e
 289       * @param PHP32 $n
 290       * @return PHP32
 291       */
 292      public function powMod(PHP32 $e, PHP32 $n)
 293      {
 294          return $this->powModOuter($e, $n);
 295      }
 296  
 297      /**
 298       * Generate a random prime number between a range
 299       *
 300       * If there's not a prime within the given range, false will be returned.
 301       *
 302       * @param PHP32 $min
 303       * @param PHP32 $max
 304       * @return false|PHP32
 305       */
 306      public static function randomRangePrime(PHP32 $min, PHP32 $max)
 307      {
 308          return self::randomRangePrimeOuter($min, $max);
 309      }
 310  
 311      /**
 312       * Generate a random number between a range
 313       *
 314       * Returns a random number between $min and $max where $min and $max
 315       * can be defined using one of the two methods:
 316       *
 317       * BigInteger::randomRange($min, $max)
 318       * BigInteger::randomRange($max, $min)
 319       *
 320       * @param PHP32 $min
 321       * @param PHP32 $max
 322       * @return PHP32
 323       */
 324      public static function randomRange(PHP32 $min, PHP32 $max)
 325      {
 326          return self::randomRangeHelper($min, $max);
 327      }
 328  
 329      /**
 330       * Performs exponentiation.
 331       *
 332       * @param PHP32 $n
 333       * @return PHP32
 334       */
 335      public function pow(PHP32 $n)
 336      {
 337          return $this->powHelper($n);
 338      }
 339  
 340      /**
 341       * Return the minimum BigInteger between an arbitrary number of BigIntegers.
 342       *
 343       * @param PHP32 ...$nums
 344       * @return PHP32
 345       */
 346      public static function min(PHP32 ...$nums)
 347      {
 348          return self::minHelper($nums);
 349      }
 350  
 351      /**
 352       * Return the maximum BigInteger between an arbitrary number of BigIntegers.
 353       *
 354       * @param PHP32 ...$nums
 355       * @return PHP32
 356       */
 357      public static function max(PHP32 ...$nums)
 358      {
 359          return self::maxHelper($nums);
 360      }
 361  
 362      /**
 363       * Tests BigInteger to see if it is between two integers, inclusive
 364       *
 365       * @param PHP32 $min
 366       * @param PHP32 $max
 367       * @return bool
 368       */
 369      public function between(PHP32 $min, PHP32 $max)
 370      {
 371          return $this->compare($min) >= 0 && $this->compare($max) <= 0;
 372      }
 373  }