1<?php
2
3/**
4 * BCMath 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 * BCMath Engine.
23 *
24 * @package BCMath
25 * @author  Jim Wigginton <terrafrost@php.net>
26 * @access  public
27 */
28class BCMath extends Engine
29{
30    /**
31     * Can Bitwise operations be done fast?
32     *
33     * @see parent::bitwise_leftRotate()
34     * @see parent::bitwise_rightRotate()
35     * @access protected
36     */
37    const FAST_BITWISE = false;
38
39    /**
40     * Engine Directory
41     *
42     * @see parent::setModExpEngine
43     * @access protected
44     */
45    const ENGINE_DIR = 'BCMath';
46
47    /**
48     * Modular Exponentiation Engine
49     *
50     * @var string
51     */
52    protected static $modexpEngine;
53
54    /**
55     * Engine Validity Flag
56     *
57     * @var bool
58     */
59    protected static $isValidEngine;
60
61    /**
62     * BigInteger(0)
63     *
64     * @var \phpseclib3\Math\BigInteger\Engines\BCMath
65     */
66    protected static $zero;
67
68    /**
69     * BigInteger(1)
70     *
71     * @var \phpseclib3\Math\BigInteger\Engines\BCMath
72     */
73    protected static $one;
74
75    /**
76     * BigInteger(2)
77     *
78     * @var \phpseclib3\Math\BigInteger\Engines\BCMath
79     */
80    protected static $two;
81
82    /**
83     * Primes > 2 and < 1000
84     *
85     * @var array
86     */
87    protected static $primes;
88
89    /**
90     * Test for engine validity
91     *
92     * @see parent::__construct()
93     * @return bool
94     */
95    public static function isValidEngine()
96    {
97        return extension_loaded('bcmath');
98    }
99
100    /**
101     * Default constructor
102     *
103     * @param mixed $x integer Base-10 number or base-$base number if $base set.
104     * @param int $base
105     * @see parent::__construct()
106     * @return \phpseclib3\Math\BigInteger\Engines\BCMath
107     */
108    public function __construct($x = 0, $base = 10)
109    {
110        if (!isset(self::$isValidEngine)) {
111            self::$isValidEngine = self::isValidEngine();
112        }
113        if (!self::$isValidEngine) {
114            throw new BadConfigurationException('BCMath is not setup correctly on this system');
115        }
116
117        $this->value = '0';
118
119        parent::__construct($x, $base);
120    }
121
122    /**
123     * Initialize a BCMath BigInteger Engine instance
124     *
125     * @param int $base
126     * @see parent::__construct()
127     */
128    protected function initialize($base)
129    {
130        switch (abs($base)) {
131            case 256:
132                // round $len to the nearest 4
133                $len = (strlen($this->value) + 3) & 0xFFFFFFFC;
134
135                $x = str_pad($this->value, $len, chr(0), STR_PAD_LEFT);
136
137                $this->value = '0';
138                for ($i = 0; $i < $len; $i+= 4) {
139                    $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32
140                    $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0);
141                }
142
143                if ($this->is_negative) {
144                    $this->value = '-' . $this->value;
145                }
146                break;
147            case 16:
148                $x = (strlen($this->value) & 1) ? '0' . $this->value : $this->value;
149                $temp = new self(Hex::decode($x), 256);
150                $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
151                $this->is_negative = false;
152                break;
153            case 10:
154                // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
155                // results then doing it on '-1' does (modInverse does $x[0])
156                $this->value = $this->value === '-' ? '0' : (string) $this->value;
157        }
158    }
159
160    /**
161     * Converts a BigInteger to a base-10 number.
162     *
163     * @return string
164     */
165    public function toString()
166    {
167        if ($this->value === '0') {
168            return '0';
169        }
170
171        return ltrim($this->value, '0');
172    }
173
174    /**
175     * Converts a BigInteger to a byte string (eg. base-256).
176     *
177     * @param bool $twos_compliment
178     * @return string
179     */
180    function toBytes($twos_compliment = false)
181    {
182        if ($twos_compliment) {
183            return $this->toBytesHelper();
184        }
185
186        $value = '';
187        $current = $this->value;
188
189        if ($current[0] == '-') {
190            $current = substr($current, 1);
191        }
192
193        while (bccomp($current, '0', 0) > 0) {
194            $temp = bcmod($current, '16777216');
195            $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
196            $current = bcdiv($current, '16777216', 0);
197        }
198
199        return $this->precision > 0 ?
200            substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
201            ltrim($value, chr(0));
202    }
203
204    /**
205     * Adds two BigIntegers.
206     *
207     * @param BCMath $y
208     * @return BCMath
209     */
210    public function add(BCMath $y)
211    {
212        $temp = new self();
213        $temp->value = bcadd($this->value, $y->value);
214
215        return $this->normalize($temp);
216    }
217
218    /**
219     * Subtracts two BigIntegers.
220     *
221     * @param BCMath $y
222     * @return BCMath
223     */
224    public function subtract(BCMath $y)
225    {
226        $temp = new self();
227        $temp->value = bcsub($this->value, $y->value);
228
229        return $this->normalize($temp);
230    }
231
232    /**
233     * Multiplies two BigIntegers.
234     *
235     * @param BCMath $x
236     * @return BCMath
237     */
238    public function multiply(BCMath $x)
239    {
240        $temp = new self();
241        $temp->value = bcmul($this->value, $x->value);
242
243        return $this->normalize($temp);
244    }
245
246    /**
247     * Divides two BigIntegers.
248     *
249     * Returns an array whose first element contains the quotient and whose second element contains the
250     * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
251     * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
252     * and the divisor (basically, the "common residue" is the first positive modulo).
253     *
254     * @param BCMath $y
255     * @return BCMath
256     */
257    public function divide(BCMath $y)
258    {
259        $quotient = new self();
260        $remainder = new self();
261
262        $quotient->value = bcdiv($this->value, $y->value, 0);
263        $remainder->value = bcmod($this->value, $y->value);
264
265        if ($remainder->value[0] == '-') {
266            $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
267        }
268
269        return [$this->normalize($quotient), $this->normalize($remainder)];
270    }
271
272    /**
273     * Calculates modular inverses.
274     *
275     * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
276     *
277     * @return false|BCMath
278     * @param \phpseclib3\Math\BigInteger\Engines\BCMath $n
279     */
280    public function modInverse(BCMath $n)
281    {
282        return $this->modInverseHelper($n);
283    }
284
285    /**
286     * Calculates the greatest common divisor and Bezout's identity.
287     *
288     * Say you have 693 and 609.  The GCD is 21.  Bezout's identity states that there exist integers x and y such that
289     * 693*x + 609*y == 21.  In point of fact, there are actually an infinite number of x and y combinations and which
290     * combination is returned is dependent upon which mode is in use.  See
291     * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.
292     *
293     * @param BCMath $n
294     * @return BCMath
295     */
296    public function extendedGCD(BCMath $n)
297    {
298        // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
299        // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway.  as is,
300        // the basic extended euclidean algorithim is what we're using.
301
302        $u = $this->value;
303        $v = $n->value;
304
305        $a = '1';
306        $b = '0';
307        $c = '0';
308        $d = '1';
309
310        while (bccomp($v, '0', 0) != 0) {
311            $q = bcdiv($u, $v, 0);
312
313            $temp = $u;
314            $u = $v;
315            $v = bcsub($temp, bcmul($v, $q, 0), 0);
316
317            $temp = $a;
318            $a = $c;
319            $c = bcsub($temp, bcmul($a, $q, 0), 0);
320
321            $temp = $b;
322            $b = $d;
323            $d = bcsub($temp, bcmul($b, $q, 0), 0);
324        }
325
326        return [
327            'gcd' => $this->normalize(new static($u)),
328            'x'   => $this->normalize(new static($a)),
329            'y'   => $this->normalize(new static($b))
330        ];
331    }
332
333    /**
334     * Calculates the greatest common divisor
335     *
336     * Say you have 693 and 609.  The GCD is 21.
337     *
338     * @param BCMath $n
339     * @return BCMath
340     */
341    public function gcd(BCMath $n)
342    {
343        extract($this->extendedGCD($n));
344        /** @var BCMath $gcd */
345        return $gcd;
346    }
347
348    /**
349     * Absolute value.
350     *
351     * @return \phpseclib3\Math\BigInteger\Engines\BCMath
352     */
353    public function abs()
354    {
355        $temp = new static();
356        $temp->value = strlen($this->value) && $this->value[0] == '-' ?
357            substr($this->value, 1) :
358            $this->value;
359
360        return $temp;
361    }
362
363    /**
364     * Logical And
365     *
366     * @param BCMath $x
367     * @return BCMath
368     */
369    public function bitwise_and(BCMath $x)
370    {
371        return $this->bitwiseAndHelper($x);
372    }
373
374    /**
375     * Logical Or
376     *
377     * @param BCMath $x
378     * @return BCMath
379     */
380    public function bitwise_or(BCMath $x)
381    {
382        return $this->bitwiseXorHelper($x);
383    }
384
385    /**
386     * Logical Exclusive Or
387     *
388     * @param BCMath $x
389     * @return BCMath
390     */
391    public function bitwise_xor(BCMath $x)
392    {
393        return $this->bitwiseXorHelper($x);
394    }
395
396    /**
397     * Logical Right Shift
398     *
399     * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
400     *
401     * @param int $shift
402     * @return \phpseclib3\Math\BigInteger\Engines\BCMath
403     */
404    public function bitwise_rightShift($shift)
405    {
406        $temp = new static();
407        $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0);
408
409        return $this->normalize($temp);
410    }
411
412    /**
413     * Logical Left Shift
414     *
415     * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
416     *
417     * @param int $shift
418     * @return \phpseclib3\Math\BigInteger\Engines\BCMath
419     */
420    public function bitwise_leftShift($shift)
421    {
422        $temp = new static();
423        $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0);
424
425        return $this->normalize($temp);
426    }
427
428    /**
429     * Compares two numbers.
430     *
431     * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite.  The reason for this is
432     * demonstrated thusly:
433     *
434     * $x  > $y: $x->compare($y)  > 0
435     * $x  < $y: $x->compare($y)  < 0
436     * $x == $y: $x->compare($y) == 0
437     *
438     * Note how the same comparison operator is used.  If you want to test for equality, use $x->equals($y).
439     *
440     * {@internal Could return $this->subtract($x), but that's not as fast as what we do do.}
441     *
442     * @param BCMath $y
443     * @return int in case < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
444     * @see self::equals()
445     */
446    public function compare(BCMath $y)
447    {
448        return bccomp($this->value, $y->value, 0);
449    }
450
451    /**
452     * Tests the equality of two numbers.
453     *
454     * If you need to see if one number is greater than or less than another number, use BigInteger::compare()
455     *
456     * @param BCMath $x
457     * @return bool
458     */
459    public function equals(BCMath $x)
460    {
461        return $this->value == $x->value;
462    }
463
464    /**
465     * Performs modular exponentiation.
466     *
467     * @param BCMath $e
468     * @param BCMath $n
469     * @return BCMath
470     */
471    public function modPow(BCMath $e, BCMath $n)
472    {
473        return $this->powModOuter($e, $n);
474    }
475
476    /**
477     * Performs modular exponentiation.
478     *
479     * Alias for modPow().
480     *
481     * @param BCMath $e
482     * @param BCMath $n
483     * @return BCMath
484     */
485    public function powMod(BCMath $e, BCMath $n)
486    {
487        return $this->powModOuter($e, $n);
488    }
489
490    /**
491     * Performs modular exponentiation.
492     *
493     * @param BCMath $e
494     * @param BCMath $n
495     * @return BCMath
496     */
497    protected function powModInner(BCMath $e, BCMath $n)
498    {
499        try {
500            $class = self::$modexpEngine;
501            return $class::powModHelper($this, $e, $n, static::class);
502        } catch (\Exception $err) {
503            return BCMath\DefaultEngine::powModHelper($this, $e, $n, static::class);
504        }
505    }
506
507    /**
508     * Normalize
509     *
510     * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
511     *
512     * @param BCMath $result
513     * @return BCMath
514     */
515    protected function normalize(BCMath $result)
516    {
517        unset($result->reduce);
518
519        $result->precision = $this->precision;
520        $result->bitmask = $this->bitmask;
521
522        if ($result->bitmask !== false) {
523            $result->value = bcmod($result->value, $result->bitmask->value);
524        }
525
526        return $result;
527    }
528
529    /**
530     * Generate a random prime number between a range
531     *
532     * If there's not a prime within the given range, false will be returned.
533     *
534     * @param BCMath $min
535     * @param BCMath $max
536     * @return false|BCMath
537     */
538    public static function randomRangePrime(BCMath $min, BCMath $max)
539    {
540        return self::randomRangePrimeOuter($min, $max);
541    }
542
543    /**
544     * Generate a random number between a range
545     *
546     * Returns a random number between $min and $max where $min and $max
547     * can be defined using one of the two methods:
548     *
549     * BigInteger::randomRange($min, $max)
550     * BigInteger::randomRange($max, $min)
551     *
552     * @param BCMath $min
553     * @param BCMath $max
554     * @return BCMath
555     */
556    public static function randomRange(BCMath $min, BCMath $max)
557    {
558        return self::randomRangeHelper($min, $max);
559    }
560
561    /**
562     * Make the current number odd
563     *
564     * If the current number is odd it'll be unchanged.  If it's even, one will be added to it.
565     *
566     * @see self::randomPrime()
567     */
568    protected function make_odd()
569    {
570        if (!$this->isOdd()) {
571            $this->value = bcadd($this->value, '1');
572        }
573    }
574
575    /**
576     * Test the number against small primes.
577     *
578     * @see self::isPrime()
579     */
580    protected function testSmallPrimes()
581    {
582        if ($this->value === '1') {
583            return false;
584        }
585        if ($this->value === '2') {
586            return true;
587        }
588        if ($this->value[strlen($this->value) - 1] % 2 == 0) {
589            return false;
590        }
591
592        $value = $this->value;
593
594        foreach (self::$primes as $prime) {
595            $r = bcmod($this->value, $prime);
596            if ($r == '0') {
597                return $this->value == $prime;
598            }
599        }
600
601        return true;
602    }
603
604    /**
605     * Scan for 1 and right shift by that amount
606     *
607     * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
608     *
609     * @see self::isPrime()
610     * @param BCMath $r
611     * @return int
612     */
613    public static function scan1divide(BCMath $r)
614    {
615        $r_value = &$r->value;
616        $s = 0;
617        // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals(static::$one) check earlier
618        while ($r_value[strlen($r_value) - 1] % 2 == 0) {
619            $r_value = bcdiv($r_value, '2', 0);
620            ++$s;
621        }
622
623        return $s;
624    }
625
626    /**
627     * Performs exponentiation.
628     *
629     * @param BCMath $n
630     * @return BCMath
631     */
632    public function pow(BCMath $n)
633    {
634        $temp = new self();
635        $temp->value = bcpow($this->value, $n->value);
636
637        return $this->normalize($temp);
638    }
639
640    /**
641     * Return the minimum BigInteger between an arbitrary number of BigIntegers.
642     *
643     * @param BCMath ...$nums
644     * @return BCMath
645     */
646    public static function min(BCMath ...$nums)
647    {
648        return self::minHelper($nums);
649    }
650
651    /**
652     * Return the maximum BigInteger between an arbitrary number of BigIntegers.
653     *
654     * @param BCMath ...$nums
655     * @return BCMath
656     */
657    public static function max(BCMath ...$nums)
658    {
659        return self::maxHelper($nums);
660    }
661
662    /**
663     * Tests BigInteger to see if it is between two integers, inclusive
664     *
665     * @param BCMath $min
666     * @param BCMath $max
667     * @return bool
668     */
669    public function between(BCMath $min, BCMath $max)
670    {
671        return $this->compare($min) >= 0 && $this->compare($max) <= 0;
672    }
673
674    /**
675     * Set Bitmask
676     *
677     * @return Engine
678     * @param int $bits
679     * @see self::setPrecision()
680     */
681    protected static function setBitmask($bits)
682    {
683        $temp = parent::setBitmask($bits);
684        return $temp->add(static::$one);
685    }
686
687    /**
688     * Is Odd?
689     *
690     * @return boolean
691     */
692    public function isOdd()
693    {
694        return $this->value[strlen($this->value) - 1] % 2 == 1;
695    }
696
697    /**
698     * Tests if a bit is set
699     *
700     * @return boolean
701     */
702    public function testBit($x)
703    {
704        return bccomp(
705            bcmod($this->value, bcpow('2', $x + 1, 0), 0),
706            bcpow('2', $x, 0),
707            0
708        ) >= 0;
709    }
710
711    /**
712     * Is Negative?
713     *
714     * @return boolean
715     */
716    public function isNegative()
717    {
718        return strlen($this->value) && $this->value[0] == '-';
719    }
720
721    /**
722     * Negate
723     *
724     * Given $k, returns -$k
725     *
726     * @return BCMath
727     */
728    public function negate()
729    {
730        $temp = clone $this;
731
732        if (!strlen($temp->value)) {
733            return $temp;
734        }
735
736        $temp->value = $temp->value[0] == '-' ?
737            substr($this->value, 1) :
738            '-' . $this->value;
739
740        return $temp;
741    }
742}