Rev 846 | Rev 1042 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
827 | daniel-mar | 1 | <?php |
2 | |||
3 | /** |
||
4 | * Pure-PHP 64-bit BigInteger Engine |
||
5 | * |
||
6 | * PHP version 5 and 7 |
||
7 | * |
||
874 | daniel-mar | 8 | * @category Math |
9 | * @package BigInteger |
||
827 | daniel-mar | 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 | |||
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 | * |
||
874 | daniel-mar | 23 | * @package PHP |
827 | daniel-mar | 24 | * @author Jim Wigginton <terrafrost@php.net> |
874 | daniel-mar | 25 | * @access public |
827 | daniel-mar | 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. |
||
874 | daniel-mar | 254 | * @access public |
827 | daniel-mar | 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 | } |