1<?php
2
3/**
4 * Pure-PHP 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;
19use phpseclib3\Exception\BadConfigurationException;
20
21/**
22 * Pure-PHP Engine.
23 *
24 * @package PHP
25 * @author  Jim Wigginton <terrafrost@php.net>
26 * @access  public
27 */
28abstract class PHP extends Engine
29{
30    /**#@+
31     * Array constants
32     *
33     * Rather than create a thousands and thousands of new BigInteger objects in repeated function calls to add() and
34     * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them.
35     *
36     * @access protected
37    */
38    /**
39     * $result[self::VALUE] contains the value.
40     */
41    const VALUE = 0;
42    /**
43     * $result[self::SIGN] contains the sign.
44     */
45    const SIGN = 1;
46    /**#@-*/
47
48    /**
49     * Karatsuba Cutoff
50     *
51     * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
52     *
53     * @access private
54     */
55    const KARATSUBA_CUTOFF = 25;
56
57    /**
58     * Can Bitwise operations be done fast?
59     *
60     * @see parent::bitwise_leftRotate()
61     * @see parent::bitwise_rightRotate()
62     * @access protected
63     */
64    const FAST_BITWISE = true;
65
66    /**
67     * Engine Directory
68     *
69     * @see parent::setModExpEngine
70     * @access protected
71     */
72    const ENGINE_DIR = 'PHP';
73
74    /**
75     * Default constructor
76     *
77     * @param mixed $x integer Base-10 number or base-$base number if $base set.
78     * @param int $base
79     * @see parent::__construct()
80     * @return \phpseclib3\Math\BigInteger\Engines\PHP
81     */
82    public function __construct($x = 0, $base = 10)
83    {
84        if (!isset(static::$isValidEngine)) {
85            static::$isValidEngine = static::isValidEngine();
86        }
87        if (!static::$isValidEngine) {
88            throw new BadConfigurationException(static::class . ' is not setup correctly on this system');
89        }
90
91        $this->value = [];
92        parent::__construct($x, $base);
93    }
94
95    /**
96     * Initialize a PHP BigInteger Engine instance
97     *
98     * @param int $base
99     * @see parent::__construct()
100     */
101    protected function initialize($base)
102    {
103        switch (abs($base)) {
104            case 16:
105                $x = (strlen($this->value) & 1) ? '0' . $this->value : $this->value;
106                $temp = new static(Hex::decode($x), 256);
107                $this->value = $temp->value;
108                break;
109            case 10:
110                $temp = new static();
111
112                $multiplier = new static();
113                $multiplier->value = [static::MAX10];
114
115                $x = $this->value;
116
117                if ($x[0] == '-') {
118                    $this->is_negative = true;
119                    $x = substr($x, 1);
120                }
121
122                $x = str_pad($x, strlen($x) + ((static::MAX10LEN - 1) * strlen($x)) % static::MAX10LEN, 0, STR_PAD_LEFT);
123                while (strlen($x)) {
124                    $temp = $temp->multiply($multiplier);
125                    $temp = $temp->add(new static($this->int2bytes(substr($x, 0, static::MAX10LEN)), 256));
126                    $x = substr($x, static::MAX10LEN);
127                }
128
129                $this->value = $temp->value;
130        }
131    }
132
133    /**
134     * Pads strings so that unpack may be used on them
135     *
136     * @param string $str
137     * @return string
138     */
139    protected function pad($str)
140    {
141        $length = strlen($str);
142
143        $pad = 4 - (strlen($str) % 4);
144
145        return str_pad($str, $length + $pad, "\0", STR_PAD_LEFT);
146    }
147
148    /**
149     * Converts a BigInteger to a base-10 number.
150     *
151     * @return string
152     */
153    public function toString()
154    {
155        if (!count($this->value)) {
156            return '0';
157        }
158
159        $temp = clone $this;
160        $temp->bitmask = false;
161        $temp->is_negative = false;
162
163        $divisor = new static();
164        $divisor->value = [static::MAX10];
165        $result = '';
166        while (count($temp->value)) {
167            list($temp, $mod) = $temp->divide($divisor);
168            $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', static::MAX10LEN, '0', STR_PAD_LEFT) . $result;
169        }
170        $result = ltrim($result, '0');
171        if (empty($result)) {
172            $result = '0';
173        }
174
175        if ($this->is_negative) {
176            $result = '-' . $result;
177        }
178
179        return $result;
180    }
181
182    /**
183     * Converts a BigInteger to a byte string (eg. base-256).
184     *
185     * @param bool $twos_compliment
186     * @return string
187     */
188    public function toBytes($twos_compliment = false)
189    {
190        if ($twos_compliment) {
191            return $this->toBytesHelper();
192        }
193
194        if (!count($this->value)) {
195            return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
196        }
197
198        $result = $this->bitwise_small_split(8);
199        $result = implode('', array_map('chr', $result));
200
201        return $this->precision > 0 ?
202            str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) :
203            $result;
204    }
205
206    /**
207     * Performs addition.
208     *
209     * @param array $x_value
210     * @param bool $x_negative
211     * @param array $y_value
212     * @param bool $y_negative
213     * @return array
214     */
215    protected static function addHelper(array $x_value, $x_negative, array $y_value, $y_negative)
216    {
217        $x_size = count($x_value);
218        $y_size = count($y_value);
219
220        if ($x_size == 0) {
221            return [
222                self::VALUE => $y_value,
223                self::SIGN => $y_negative
224            ];
225        } elseif ($y_size == 0) {
226            return [
227                self::VALUE => $x_value,
228                self::SIGN => $x_negative
229            ];
230        }
231
232        // subtract, if appropriate
233        if ($x_negative != $y_negative) {
234            if ($x_value == $y_value) {
235                return [
236                    self::VALUE => [],
237                    self::SIGN => false
238                ];
239            }
240
241            $temp = self::subtractHelper($x_value, false, $y_value, false);
242            $temp[self::SIGN] = self::compareHelper($x_value, false, $y_value, false) > 0 ?
243                                          $x_negative : $y_negative;
244
245            return $temp;
246        }
247
248        if ($x_size < $y_size) {
249            $size = $x_size;
250            $value = $y_value;
251        } else {
252            $size = $y_size;
253            $value = $x_value;
254        }
255
256        $value[count($value)] = 0; // just in case the carry adds an extra digit
257
258        $carry = 0;
259        for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) {
260            //$sum = $x_value[$j] * static::BASE_FULL + $x_value[$i] + $y_value[$j] * static::BASE_FULL + $y_value[$i] + $carry;
261            $sum = ($x_value[$j] + $y_value[$j]) * static::BASE_FULL + $x_value[$i] + $y_value[$i] + $carry;
262            $carry = $sum >= static::MAX_DIGIT2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
263            $sum = $carry ? $sum - static::MAX_DIGIT2 : $sum;
264
265            $temp = static::BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
266
267            $value[$i] = (int) ($sum - static::BASE_FULL * $temp); // eg. a faster alternative to fmod($sum, 0x4000000)
268            $value[$j] = $temp;
269        }
270
271        if ($j == $size) { // ie. if $y_size is odd
272            $sum = $x_value[$i] + $y_value[$i] + $carry;
273            $carry = $sum >= static::BASE_FULL;
274            $value[$i] = $carry ? $sum - static::BASE_FULL : $sum;
275            ++$i; // ie. let $i = $j since we've just done $value[$i]
276        }
277
278        if ($carry) {
279            for (; $value[$i] == static::MAX_DIGIT; ++$i) {
280                $value[$i] = 0;
281            }
282            ++$value[$i];
283        }
284
285        return [
286            self::VALUE => self::trim($value),
287            self::SIGN => $x_negative
288        ];
289    }
290
291    /**
292     * Performs subtraction.
293     *
294     * @param array $x_value
295     * @param bool $x_negative
296     * @param array $y_value
297     * @param bool $y_negative
298     * @return array
299     */
300    static function subtractHelper(array $x_value, $x_negative, array $y_value, $y_negative)
301    {
302        $x_size = count($x_value);
303        $y_size = count($y_value);
304
305        if ($x_size == 0) {
306            return [
307                self::VALUE => $y_value,
308                self::SIGN => !$y_negative
309            ];
310        } elseif ($y_size == 0) {
311            return [
312                self::VALUE => $x_value,
313                self::SIGN => $x_negative
314            ];
315        }
316
317        // add, if appropriate (ie. -$x - +$y or +$x - -$y)
318        if ($x_negative != $y_negative) {
319            $temp = self::addHelper($x_value, false, $y_value, false);
320            $temp[self::SIGN] = $x_negative;
321
322            return $temp;
323        }
324
325        $diff = self::compareHelper($x_value, $x_negative, $y_value, $y_negative);
326
327        if (!$diff) {
328            return [
329                self::VALUE => [],
330                self::SIGN => false
331            ];
332        }
333
334        // switch $x and $y around, if appropriate.
335        if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) {
336            $temp = $x_value;
337            $x_value = $y_value;
338            $y_value = $temp;
339
340            $x_negative = !$x_negative;
341
342            $x_size = count($x_value);
343            $y_size = count($y_value);
344        }
345
346        // at this point, $x_value should be at least as big as - if not bigger than - $y_value
347
348        $carry = 0;
349        for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) {
350            $sum = ($x_value[$j] - $y_value[$j]) * static::BASE_FULL + $x_value[$i] - $y_value[$i] - $carry;
351
352            $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
353            $sum = $carry ? $sum + static::MAX_DIGIT2 : $sum;
354
355            $temp = static::BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
356
357            $x_value[$i] = (int) ($sum - static::BASE_FULL * $temp);
358            $x_value[$j] = $temp;
359        }
360
361        if ($j == $y_size) { // ie. if $y_size is odd
362            $sum = $x_value[$i] - $y_value[$i] - $carry;
363            $carry = $sum < 0;
364            $x_value[$i] = $carry ? $sum + static::BASE_FULL : $sum;
365            ++$i;
366        }
367
368        if ($carry) {
369            for (; !$x_value[$i]; ++$i) {
370                $x_value[$i] = static::MAX_DIGIT;
371            }
372            --$x_value[$i];
373        }
374
375        return [
376            self::VALUE => self::trim($x_value),
377            self::SIGN => $x_negative
378        ];
379    }
380
381    /**
382     * Performs multiplication.
383     *
384     * @param array $x_value
385     * @param bool $x_negative
386     * @param array $y_value
387     * @param bool $y_negative
388     * @return array
389     */
390    protected static function multiplyHelper(array $x_value, $x_negative, array $y_value, $y_negative)
391    {
392        //if ( $x_value == $y_value ) {
393        //    return [
394        //        self::VALUE => self::square($x_value),
395        //        self::SIGN => $x_sign != $y_value
396        //    ];
397        //}
398
399        $x_length = count($x_value);
400        $y_length = count($y_value);
401
402        if (!$x_length || !$y_length) { // a 0 is being multiplied
403            return [
404                self::VALUE => [],
405                self::SIGN => false
406            ];
407        }
408
409        return [
410            self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ?
411                self::trim(self::regularMultiply($x_value, $y_value)) :
412                self::trim(self::karatsuba($x_value, $y_value)),
413            self::SIGN => $x_negative != $y_negative
414        ];
415    }
416
417    /**
418     * Performs Karatsuba multiplication on two BigIntegers
419     *
420     * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
421     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.
422     *
423     * @param array $x_value
424     * @param array $y_value
425     * @return array
426     */
427    private static function karatsuba(array $x_value, array $y_value)
428    {
429        $m = min(count($x_value) >> 1, count($y_value) >> 1);
430
431        if ($m < self::KARATSUBA_CUTOFF) {
432            return self::regularMultiply($x_value, $y_value);
433        }
434
435        $x1 = array_slice($x_value, $m);
436        $x0 = array_slice($x_value, 0, $m);
437        $y1 = array_slice($y_value, $m);
438        $y0 = array_slice($y_value, 0, $m);
439
440        $z2 = self::karatsuba($x1, $y1);
441        $z0 = self::karatsuba($x0, $y0);
442
443        $z1 = self::addHelper($x1, false, $x0, false);
444        $temp = self::addHelper($y1, false, $y0, false);
445        $z1 = self::karatsuba($z1[self::VALUE], $temp[self::VALUE]);
446        $temp = self::addHelper($z2, false, $z0, false);
447        $z1 = self::subtractHelper($z1, false, $temp[self::VALUE], false);
448
449        $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
450        $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]);
451
452        $xy = self::addHelper($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
453        $xy = self::addHelper($xy[self::VALUE], $xy[self::SIGN], $z0, false);
454
455        return $xy[self::VALUE];
456    }
457
458    /**
459     * Performs long multiplication on two BigIntegers
460     *
461     * Modeled after 'multiply' in MutableBigInteger.java.
462     *
463     * @param array $x_value
464     * @param array $y_value
465     * @return array
466     */
467    protected static function regularMultiply(array $x_value, array $y_value)
468    {
469        $x_length = count($x_value);
470        $y_length = count($y_value);
471
472        if (!$x_length || !$y_length) { // a 0 is being multiplied
473            return [];
474        }
475
476        $product_value = self::array_repeat(0, $x_length + $y_length);
477
478        // the following for loop could be removed if the for loop following it
479        // (the one with nested for loops) initially set $i to 0, but
480        // doing so would also make the result in one set of unnecessary adds,
481        // since on the outermost loops first pass, $product->value[$k] is going
482        // to always be 0
483
484        $carry = 0;
485        for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0
486            $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
487            $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
488            $product_value[$j] = (int) ($temp - static::BASE_FULL * $carry);
489        }
490
491        $product_value[$j] = $carry;
492
493        // the above for loop is what the previous comment was talking about.  the
494        // following for loop is the "one with nested for loops"
495        for ($i = 1; $i < $y_length; ++$i) {
496            $carry = 0;
497
498            for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) {
499                $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
500                $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
501                $product_value[$k] = (int) ($temp - static::BASE_FULL * $carry);
502            }
503
504            $product_value[$k] = $carry;
505        }
506
507        return $product_value;
508    }
509
510    /**
511     * Divides two BigIntegers.
512     *
513     * Returns an array whose first element contains the quotient and whose second element contains the
514     * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
515     * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
516     * and the divisor (basically, the "common residue" is the first positive modulo).
517     *
518     * @param \phpseclib3\Math\BigInteger\engines\PHP $y
519     * @return array
520     * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}.
521     */
522    protected function divideHelper(PHP $y)
523    {
524        if (count($y->value) == 1) {
525            list($q, $r) = $this->divide_digit($this->value, $y->value[0]);
526            $quotient = new static();
527            $remainder = new static();
528            $quotient->value = $q;
529            $remainder->value = [$r];
530            $quotient->is_negative = $this->is_negative != $y->is_negative;
531            return [$this->normalize($quotient), $this->normalize($remainder)];
532        }
533
534        $x = clone $this;
535        $y = clone $y;
536
537        $x_sign = $x->is_negative;
538        $y_sign = $y->is_negative;
539
540        $x->is_negative = $y->is_negative = false;
541
542        $diff = $x->compare($y);
543
544        if (!$diff) {
545            $temp = new static();
546            $temp->value = [1];
547            $temp->is_negative = $x_sign != $y_sign;
548            return [$this->normalize($temp), $this->normalize(static::$zero)];
549        }
550
551        if ($diff < 0) {
552            // if $x is negative, "add" $y.
553            if ($x_sign) {
554                $x = $y->subtract($x);
555            }
556            return [$this->normalize(static::$zero), $this->normalize($x)];
557        }
558
559        // normalize $x and $y as described in HAC 14.23 / 14.24
560        $msb = $y->value[count($y->value) - 1];
561        for ($shift = 0; !($msb & static::MSB); ++$shift) {
562            $msb <<= 1;
563        }
564        $x->lshift($shift);
565        $y->lshift($shift);
566        $y_value = &$y->value;
567
568        $x_max = count($x->value) - 1;
569        $y_max = count($y->value) - 1;
570
571        $quotient = new static();
572        $quotient_value = &$quotient->value;
573        $quotient_value = self::array_repeat(0, $x_max - $y_max + 1);
574
575        static $temp, $lhs, $rhs;
576        if (!isset($temp)) {
577            $temp = new static();
578            $lhs =  new static();
579            $rhs =  new static();
580        }
581        $temp_value = &$temp->value;
582        $rhs_value =  &$rhs->value;
583
584        // $temp = $y << ($x_max - $y_max-1) in base 2**26
585        $temp_value = array_merge(self::array_repeat(0, $x_max - $y_max), $y_value);
586
587        while ($x->compare($temp) >= 0) {
588            // calculate the "common residue"
589            ++$quotient_value[$x_max - $y_max];
590            $x = $x->subtract($temp);
591            $x_max = count($x->value) - 1;
592        }
593
594        for ($i = $x_max; $i >= $y_max + 1; --$i) {
595            $x_value = &$x->value;
596            $x_window = [
597                isset($x_value[$i]) ? $x_value[$i] : 0,
598                isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0,
599                isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0
600            ];
601            $y_window = [
602                $y_value[$y_max],
603                ($y_max > 0) ? $y_value[$y_max - 1] : 0
604            ];
605
606            $q_index = $i - $y_max - 1;
607            if ($x_window[0] == $y_window[0]) {
608                $quotient_value[$q_index] = static::MAX_DIGIT;
609            } else {
610                $quotient_value[$q_index] = self::safe_divide(
611                    $x_window[0] * static::BASE_FULL + $x_window[1],
612                    $y_window[0]
613                );
614            }
615
616            $temp_value = [$y_window[1], $y_window[0]];
617
618            $lhs->value = [$quotient_value[$q_index]];
619            $lhs = $lhs->multiply($temp);
620
621            $rhs_value = [$x_window[2], $x_window[1], $x_window[0]];
622
623            while ($lhs->compare($rhs) > 0) {
624                --$quotient_value[$q_index];
625
626                $lhs->value = [$quotient_value[$q_index]];
627                $lhs = $lhs->multiply($temp);
628            }
629
630            $adjust = self::array_repeat(0, $q_index);
631            $temp_value = [$quotient_value[$q_index]];
632            $temp = $temp->multiply($y);
633            $temp_value = &$temp->value;
634            if (count($temp_value)) {
635                $temp_value = array_merge($adjust, $temp_value);
636            }
637
638            $x = $x->subtract($temp);
639
640            if ($x->compare(static::$zero) < 0) {
641                $temp_value = array_merge($adjust, $y_value);
642                $x = $x->add($temp);
643
644                --$quotient_value[$q_index];
645            }
646
647            $x_max = count($x_value) - 1;
648        }
649
650        // unnormalize the remainder
651        $x->rshift($shift);
652
653        $quotient->is_negative = $x_sign != $y_sign;
654
655        // calculate the "common residue", if appropriate
656        if ($x_sign) {
657            $y->rshift($shift);
658            $x = $y->subtract($x);
659        }
660
661        return [$this->normalize($quotient), $this->normalize($x)];
662    }
663
664    /**
665     * Divides a BigInteger by a regular integer
666     *
667     * abc / x = a00 / x + b0 / x + c / x
668     *
669     * @param array $dividend
670     * @param int $divisor
671     * @return array
672     */
673    private static function divide_digit(array $dividend, $divisor)
674    {
675        $carry = 0;
676        $result = [];
677
678        for ($i = count($dividend) - 1; $i >= 0; --$i) {
679            $temp = static::BASE_FULL * $carry + $dividend[$i];
680            $result[$i] = self::safe_divide($temp, $divisor);
681            $carry = (int) ($temp - $divisor * $result[$i]);
682        }
683
684        return [$result, $carry];
685    }
686
687    /**
688     * Single digit division
689     *
690     * Even if int64 is being used the division operator will return a float64 value
691     * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't
692     * have the precision of int64 this is a problem so, when int64 is being used,
693     * we'll guarantee that the dividend is divisible by first subtracting the remainder.
694     *
695     * @param int $x
696     * @param int $y
697     * @return int
698     */
699    private static function safe_divide($x, $y)
700    {
701        if (static::BASE === 26) {
702            return (int) ($x / $y);
703        }
704
705        // static::BASE === 31
706        return ($x - ($x % $y)) / $y;
707    }
708
709    /*
710     * Convert an array / boolean to a PHP BigInteger object
711     *
712     * @param array $arr
713     * @return \phpseclib3\Math\BigInteger\Engines\PHP
714     */
715    protected function convertToObj(array $arr)
716    {
717        $result = new static();
718        $result->value = $arr[self::VALUE];
719        $result->is_negative = $arr[self::SIGN];
720
721        return $this->normalize($result);
722    }
723
724    /**
725     * Normalize
726     *
727     * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
728     *
729     * @param PHP $result
730     * @return PHP
731     */
732    protected function normalize(PHP $result)
733    {
734        unset($result->reduce);
735
736        $result->precision = $this->precision;
737        $result->bitmask = $this->bitmask;
738
739        $value = &$result->value;
740
741        if (!count($value)) {
742            $result->is_negative = false;
743            return $result;
744        }
745
746        $value = static::trim($value);
747
748        if (!empty($result->bitmask->value)) {
749            $length = min(count($value), count($result->bitmask->value));
750            $value = array_slice($value, 0, $length);
751
752            for ($i = 0; $i < $length; ++$i) {
753                $value[$i] = $value[$i] & $result->bitmask->value[$i];
754            }
755        }
756
757        return $result;
758    }
759
760    /*
761     * Compares two numbers.
762     *
763     * @param array $x_value
764     * @param bool $x_negative
765     * @param array $y_value
766     * @param bool $y_negative
767     * @return int
768     * @see static::compare()
769     */
770    protected static function compareHelper(array $x_value, $x_negative, array $y_value, $y_negative)
771    {
772        if ($x_negative != $y_negative) {
773            return (!$x_negative && $y_negative) ? 1 : -1;
774        }
775
776        $result = $x_negative ? -1 : 1;
777
778        if (count($x_value) != count($y_value)) {
779            return (count($x_value) > count($y_value)) ? $result : -$result;
780        }
781        $size = max(count($x_value), count($y_value));
782
783        $x_value = array_pad($x_value, $size, 0);
784        $y_value = array_pad($y_value, $size, 0);
785
786        for ($i = count($x_value) - 1; $i >= 0; --$i) {
787            if ($x_value[$i] != $y_value[$i]) {
788                return ($x_value[$i] > $y_value[$i]) ? $result : -$result;
789            }
790        }
791
792        return 0;
793    }
794
795    /**
796     * Absolute value.
797     *
798     * @return \phpseclib3\Math\BigInteger\Engines\PHP
799     */
800    public function abs()
801    {
802        $temp = new static();
803        $temp->value = $this->value;
804
805        return $temp;
806    }
807
808    /**
809     * Trim
810     *
811     * Removes leading zeros
812     *
813     * @param array $value
814     * @return PHP
815     */
816    protected static function trim(array $value)
817    {
818        for ($i = count($value) - 1; $i >= 0; --$i) {
819            if ($value[$i]) {
820                break;
821            }
822            unset($value[$i]);
823        }
824
825        return $value;
826    }
827
828    /**
829     * Logical Right Shift
830     *
831     * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
832     *
833     * @param int $shift
834     * @return \phpseclib3\Math\BigInteger\Engines\PHP
835     */
836    public function bitwise_rightShift($shift)
837    {
838        $temp = new static();
839
840        // could just replace lshift with this, but then all lshift() calls would need to be rewritten
841        // and I don't want to do that...
842        $temp->value = $this->value;
843        $temp->rshift($shift);
844
845        return $this->normalize($temp);
846    }
847
848    /**
849     * Logical Left Shift
850     *
851     * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
852     *
853     * @param int $shift
854     * @return \phpseclib3\Math\BigInteger\Engines\PHP
855     */
856    public function bitwise_leftShift($shift)
857    {
858        $temp = new static();
859        // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
860        // and I don't want to do that...
861        $temp->value = $this->value;
862        $temp->lshift($shift);
863
864        return $this->normalize($temp);
865    }
866
867    /**
868     * Converts 32-bit integers to bytes.
869     *
870     * @param int $x
871     * @return string
872     */
873    private static function int2bytes($x)
874    {
875        return ltrim(pack('N', $x), chr(0));
876    }
877
878    /**
879     * Array Repeat
880     *
881     * @param int $input
882     * @param int $multiplier
883     * @return array
884     */
885    protected static function array_repeat($input, $multiplier)
886    {
887        return $multiplier ? array_fill(0, $multiplier, $input) : [];
888    }
889
890    /**
891     * Logical Left Shift
892     *
893     * Shifts BigInteger's by $shift bits.
894     *
895     * @param int $shift
896     */
897    protected function lshift($shift)
898    {
899        if ($shift == 0) {
900            return;
901        }
902
903        $num_digits = (int) ($shift / static::BASE);
904        $shift %= static::BASE;
905        $shift = 1 << $shift;
906
907        $carry = 0;
908
909        for ($i = 0; $i < count($this->value); ++$i) {
910            $temp = $this->value[$i] * $shift + $carry;
911            $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
912            $this->value[$i] = (int) ($temp - $carry * static::BASE_FULL);
913        }
914
915        if ($carry) {
916            $this->value[count($this->value)] = $carry;
917        }
918
919        while ($num_digits--) {
920            array_unshift($this->value, 0);
921        }
922    }
923
924    /**
925     * Logical Right Shift
926     *
927     * Shifts BigInteger's by $shift bits.
928     *
929     * @param int $shift
930     */
931    protected function rshift($shift)
932    {
933        if ($shift == 0) {
934            return;
935        }
936
937        $num_digits = (int) ($shift / static::BASE);
938        $shift %= static::BASE;
939        $carry_shift = static::BASE - $shift;
940        $carry_mask = (1 << $shift) - 1;
941
942        if ($num_digits) {
943            $this->value = array_slice($this->value, $num_digits);
944        }
945
946        $carry = 0;
947
948        for ($i = count($this->value) - 1; $i >= 0; --$i) {
949            $temp = $this->value[$i] >> $shift | $carry;
950            $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
951            $this->value[$i] = $temp;
952        }
953
954        $this->value = static::trim($this->value);
955    }
956
957    /**
958     * Performs modular exponentiation.
959     *
960     * @param PHP $e
961     * @param PHP $n
962     * @return PHP
963     */
964    protected function powModInner(PHP $e, PHP $n)
965    {
966        try {
967            $class = static::$modexpEngine;
968            return $class::powModHelper($this, $e, $n, static::class);
969        } catch (\Exception $err) {
970            return PHP\DefaultEngine::powModHelper($this, $e, $n, static::class);
971        }
972    }
973
974    /**
975     * Performs squaring
976     *
977     * @param array $x
978     * @return array
979     */
980    protected static function square(array $x)
981    {
982        return count($x) < 2 * self::KARATSUBA_CUTOFF ?
983            self::trim(self::baseSquare($x)) :
984            self::trim(self::karatsubaSquare($x));
985    }
986
987    /**
988     * Performs traditional squaring on two BigIntegers
989     *
990     * Squaring can be done faster than multiplying a number by itself can be.  See
991     * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} /
992     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.
993     *
994     * @param array $value
995     * @return array
996     */
997    protected static function baseSquare(array $value)
998    {
999        if (empty($value)) {
1000            return [];
1001        }
1002        $square_value = self::array_repeat(0, 2 * count($value));
1003
1004        for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) {
1005            $i2 = $i << 1;
1006
1007            $temp = $square_value[$i2] + $value[$i] * $value[$i];
1008            $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1009            $square_value[$i2] = (int) ($temp - static::BASE_FULL * $carry);
1010
1011            // note how we start from $i+1 instead of 0 as we do in multiplication.
1012            for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) {
1013                $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry;
1014                $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1015                $square_value[$k] = (int) ($temp - static::BASE_FULL * $carry);
1016            }
1017
1018            // the following line can yield values larger 2**15.  at this point, PHP should switch
1019            // over to floats.
1020            $square_value[$i + $max_index + 1] = $carry;
1021        }
1022
1023        return $square_value;
1024    }
1025
1026    /**
1027     * Performs Karatsuba "squaring" on two BigIntegers
1028     *
1029     * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
1030     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.
1031     *
1032     * @param array $value
1033     * @return array
1034     */
1035    protected static function karatsubaSquare(array $value)
1036    {
1037        $m = count($value) >> 1;
1038
1039        if ($m < self::KARATSUBA_CUTOFF) {
1040            return self::baseSquare($value);
1041        }
1042
1043        $x1 = array_slice($value, $m);
1044        $x0 = array_slice($value, 0, $m);
1045
1046        $z2 = self::karatsubaSquare($x1);
1047        $z0 = self::karatsubaSquare($x0);
1048
1049        $z1 = self::addHelper($x1, false, $x0, false);
1050        $z1 = self::karatsubaSquare($z1[self::VALUE]);
1051        $temp = self::addHelper($z2, false, $z0, false);
1052        $z1 = self::subtractHelper($z1, false, $temp[self::VALUE], false);
1053
1054        $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1055        $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]);
1056
1057        $xx = self::addHelper($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
1058        $xx = self::addHelper($xx[self::VALUE], $xx[self::SIGN], $z0, false);
1059
1060        return $xx[self::VALUE];
1061    }
1062
1063    /**
1064     * Make the current number odd
1065     *
1066     * If the current number is odd it'll be unchanged.  If it's even, one will be added to it.
1067     *
1068     * @see self::randomPrime()
1069     */
1070    protected function make_odd()
1071    {
1072        $this->value[0] |= 1;
1073    }
1074
1075    /**
1076     * Test the number against small primes.
1077     *
1078     * @see self::isPrime()
1079     */
1080    protected function testSmallPrimes()
1081    {
1082        if ($this->value == [1]) {
1083            return false;
1084        }
1085        if ($this->value == [2]) {
1086            return true;
1087        }
1088        if (~$this->value[0] & 1) {
1089            return false;
1090        }
1091
1092        $value = $this->value;
1093        foreach (static::$primes as $prime) {
1094            list(, $r) = self::divide_digit($value, $prime);
1095            if (!$r) {
1096                return count($value) == 1 && $value[0] == $prime;
1097            }
1098        }
1099
1100        return true;
1101    }
1102
1103    /**
1104     * Scan for 1 and right shift by that amount
1105     *
1106     * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
1107     *
1108     * @see self::isPrime()
1109     * @param PHP $r
1110     * @return int
1111     */
1112    public static function scan1divide(PHP $r)
1113    {
1114        $r_value = &$r->value;
1115        for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) {
1116            $temp = ~$r_value[$i] & static::MAX_DIGIT;
1117            for ($j = 1; ($temp >> $j) & 1; ++$j) {
1118            }
1119            if ($j <= static::BASE) {
1120                break;
1121            }
1122        }
1123        $s = static::BASE * $i + $j;
1124        $r->rshift($s);
1125        return $s;
1126    }
1127
1128    /**
1129     * Performs exponentiation.
1130     *
1131     * @param PHP $n
1132     * @return PHP
1133     */
1134    protected function powHelper(PHP $n)
1135    {
1136        if ($n->compare(static::$zero) == 0) {
1137            return new static(1);
1138        } // n^0 = 1
1139
1140        $temp = clone $this;
1141        while (!$n->equals(static::$one)) {
1142            $temp = $temp->multiply($this);
1143            $n = $n->subtract(static::$one);
1144        }
1145
1146        return $temp;
1147    }
1148
1149    /**
1150     * Is Odd?
1151     *
1152     * @return boolean
1153     */
1154    public function isOdd()
1155    {
1156        return (bool) ($this->value[0] & 1);
1157    }
1158
1159    /**
1160     * Tests if a bit is set
1161     *
1162     * @return boolean
1163     */
1164    public function testBit($x)
1165    {
1166        $digit = floor($x / static::BASE);
1167        $bit = $x % static::BASE;
1168
1169        if (!isset($this->value[$digit])) {
1170            return false;
1171        }
1172
1173        return (bool) ($this->value[$digit] & (1 << $bit));
1174    }
1175
1176    /**
1177     * Is Negative?
1178     *
1179     * @return boolean
1180     */
1181    public function isNegative()
1182    {
1183        return $this->is_negative;
1184    }
1185
1186    /**
1187     * Negate
1188     *
1189     * Given $k, returns -$k
1190     *
1191     * @return BigInteger
1192     */
1193    public function negate()
1194    {
1195        $temp = clone $this;
1196        $temp->is_negative = !$temp->is_negative;
1197
1198        return $temp;
1199    }
1200
1201    /**
1202     * Bitwise Split
1203     *
1204     * Splits BigInteger's into chunks of $split bits
1205     *
1206     * @param int $split
1207     * @return \phpseclib3\Math\BigInteger\Engines\PHP[]
1208     */
1209    public function bitwise_split($split)
1210    {
1211        if ($split < 1) {
1212            throw new \RuntimeException('Offset must be greater than 1');
1213        }
1214
1215        $width = (int) ($split / static::BASE);
1216        if (!$width) {
1217            $arr = $this->bitwise_small_split($split);
1218            return array_map(function ($digit) {
1219                $temp = new static();
1220                $temp->value = $digit != 0 ? [$digit] : [];
1221                return $temp;
1222            }, $arr);
1223        }
1224
1225        $vals = [];
1226        $val = $this->value;
1227
1228        $i = $overflow = 0;
1229        $len = count($val);
1230        while ($i < $len) {
1231            $digit = [];
1232            if (!$overflow) {
1233                $digit = array_slice($val, $i, $width);
1234                $i+= $width;
1235                $overflow = $split % static::BASE;
1236                if ($overflow) {
1237                    $mask = (1 << $overflow) - 1;
1238                    $temp = isset($val[$i]) ? $val[$i] : 0;
1239                    $digit[] = $temp & $mask;
1240                }
1241            } else {
1242                $remaining = static::BASE - $overflow;
1243                $tempsplit = $split - $remaining;
1244                $tempwidth = (int) ($tempsplit / static::BASE + 1);
1245                $digit = array_slice($val, $i, $tempwidth);
1246                $i+= $tempwidth;
1247                $tempoverflow = $tempsplit % static::BASE;
1248                if ($tempoverflow) {
1249                    $tempmask = (1 << $tempoverflow) - 1;
1250                    $temp = isset($val[$i]) ? $val[$i] : 0;
1251                    $digit[] = $temp & $tempmask;
1252                }
1253                $newbits = 0;
1254                for ($j = count($digit) - 1; $j >= 0; $j--) {
1255                    $temp = $digit[$j] & $mask;
1256                    $digit[$j] = ($digit[$j] >> $overflow) | ($newbits << $remaining);
1257                    $newbits = $temp;
1258                }
1259                $overflow = $tempoverflow;
1260                $mask = $tempmask;
1261            }
1262            $temp = new static();
1263            $temp->value = static::trim($digit);
1264            $vals[] = $temp;
1265        }
1266
1267        return array_reverse($vals);
1268    }
1269
1270    /**
1271     * Bitwise Split where $split < static::BASE
1272     *
1273     * @param int $split
1274     * @return \phpseclib3\Math\BigInteger\Engines\PHP[]
1275     */
1276    private function bitwise_small_split($split)
1277    {
1278        $vals = [];
1279        $val = $this->value;
1280
1281        $mask = (1 << $split) - 1;
1282
1283        $i = $overflow = 0;
1284        $len = count($val);
1285        $val[] = 0;
1286        $remaining = static::BASE;
1287        while ($i != $len) {
1288            $digit = $val[$i] & $mask;
1289            $val[$i]>>= $split;
1290            if (!$overflow) {
1291                $remaining-= $split;
1292                $overflow = $split <= $remaining ? 0 : $split - $remaining;
1293
1294                if (!$remaining) {
1295                    $i++;
1296                    $remaining = static::BASE;
1297                    $overflow = 0;
1298                }
1299            } else if (++$i != $len) {
1300                $tempmask = (1 << $overflow) - 1;
1301                $digit|= ($val[$i] & $tempmask) << $remaining;
1302                $val[$i]>>= $overflow;
1303                $remaining = static::BASE - $overflow;
1304                $overflow = $split <= $remaining ? 0 : $split - $remaining;
1305            }
1306
1307            $vals[] = $digit;
1308        }
1309
1310        while ($vals[count($vals) - 1] == 0) {
1311            unset($vals[count($vals) - 1]);
1312        }
1313
1314        return array_reverse($vals);
1315    }
1316}