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