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