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 <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 64-bit Engine. 20 * 21 * Uses 64-bit integers if int size is 8 bits 22 * 23 * @package PHP 24 * @author Jim Wigginton <terrafrost@php.net> 25 * @access public 26 */ 27class 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} 378