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