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