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