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 <terrafrost@php.net> 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 16namespace 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 <terrafrost@php.net> 25 * @access public 26 */ 27class 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} 374