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