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