<?php

/**
 * BCMath BigInteger Engine
 *
 * PHP version 8.1+
 *
 * @author    Jim Wigginton <terrafrost@php.net>
 * @copyright 2017-2026 Jim Wigginton
 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
 * @link      https://phpseclib.com/
 */

declare(strict_types=1);

namespace phpseclib4\Math\BigInteger\Engines;

use phpseclib4\Common\Functions\Strings;
use phpseclib4\Exception\BadConfigurationException;

/**
 * BCMath Engine.
 *
 * @author  Jim Wigginton <terrafrost@php.net>
 * @psalm-api
 */
class BCMath extends Engine
{
    /**
     * Can Bitwise operations be done fast?
     *
     * @see parent::bitwise_leftRotate()
     * @see parent::bitwise_rightRotate()
     */
    public const FAST_BITWISE = false;

    /**
     * Engine Directory
     *
     * @see parent::setModExpEngine
     */
    public const ENGINE_DIR = 'BCMath';

    /**
     * Test for engine validity
     *
     * @see parent::__construct()
     */
    public static function isValidEngine(): bool
    {
        return extension_loaded('bcmath');
    }

    /**
     * Default constructor
     *
     * @param mixed $x integer Base-10 number or base-$base number if $base set.
     * @see parent::__construct()
     */
    public function __construct(int|string|\GMP $x = 0, int $base = 10)
    {
        if (!isset(static::$isValidEngine[static::class])) {
            static::$isValidEngine[static::class] = self::isValidEngine();
        }
        if (!static::$isValidEngine[static::class]) {
            throw new BadConfigurationException('BCMath is not setup correctly on this system');
        }

        $this->value = '0';

        parent::__construct($x, $base);
    }

    /**
     * Initialize a BCMath BigInteger Engine instance
     *
     * @see parent::__construct()
     */
    protected function initialize(int $base): void
    {
        switch (abs($base)) {
            case 256:
                // round $len to the nearest 4
                $len = (strlen($this->value) + 3) & ~3;

                $x = str_pad($this->value, $len, chr(0), STR_PAD_LEFT);

                $this->value = '0';
                for ($i = 0; $i < $len; $i += 4) {
                    $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32
                    $temp = sprintf('%u', unpack('N', substr($x, $i, 4))[1]);
                    $this->value = bcadd($this->value, $temp, 0);
                }

                if ($this->is_negative) {
                    $this->value = '-' . $this->value;
                }
                break;
            case 16:
                $x = (strlen($this->value) & 1) ? '0' . $this->value : $this->value;
                $temp = new static(Strings::hex2bin($x), 256);
                $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
                $this->is_negative = false;
                break;
            case 10:
                // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
                // results then doing it on '-1' does (modInverse does $x[0])
                $this->value = $this->value === '-' ? '0' : (string) $this->value;
        }
    }

    /**
     * Converts a BigInteger to a base-10 number.
     */
    public function toString(): string
    {
        if ($this->value === '0') {
            return '0';
        }

        return ltrim($this->value, '0');
    }

    /**
     * Converts a BigInteger to a byte string (eg. base-256).
     */
    public function toBytes(bool $twos_compliment = false): string
    {
        if ($twos_compliment) {
            return $this->toBytesHelper();
        }

        $value = '';
        $current = $this->value;

        if ($current[0] == '-') {
            $current = substr($current, 1);
        }

        while (bccomp($current, '0', 0) > 0) {
            $quotient = bcdiv($current, '4294967296', 0);
            $remainder = bcsub($current, bcmul($quotient, '4294967296', 0), 0);
            $temp = (int) ($remainder / 256); // ie. >> 8
            $value = chr($temp >> 16) . // ie. $remainder >> 24
                chr(($temp >> 8) & 0xFF) . // ie. $remainder >> 16
                chr($temp & 0xFF) . // i. $remainder >> 8
                //chr((int) ($remainder - 256 * $temp)) .
                chr((int) fmod(floatval($remainder), 256)) .
                $value;
            $current = $quotient;
        }

        return $this->precision > 0 ?
            substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
            ltrim($value, chr(0));
    }

    /**
     * Adds two BigIntegers.
     */
    public function add(BCMath $y): static
    {
        $temp = new static();
        $temp->value = bcadd($this->value, $y->value, 0);

        return $this->normalize($temp);
    }

    /**
     * Subtracts two BigIntegers.
     */
    public function subtract(BCMath $y): static
    {
        $temp = new static();
        $temp->value = bcsub($this->value, $y->value, 0);

        return $this->normalize($temp);
    }

    /**
     * Multiplies two BigIntegers.
     */
    public function multiply(BCMath $x): static
    {
        $temp = new static();
        $temp->value = bcmul($this->value, $x->value, 0);

        return $this->normalize($temp);
    }

    /**
     * Divides two BigIntegers.
     *
     * Returns an array whose first element contains the quotient and whose second element contains the
     * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
     * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
     * and the divisor (basically, the "common residue" is the first positive modulo).
     *
     * @return array{static, static}
     */
    public function divide(BCMath $y): array
    {
        $quotient = new static();
        $remainder = new static();

        $quotient->value = bcdiv($this->value, $y->value, 0);
        $remainder->value = bcmod($this->value, $y->value, 0);

        if ($remainder->value[0] == '-') {
            $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
        }

        return [$this->normalize($quotient), $this->normalize($remainder)];
    }

    /**
     * Calculates modular inverses.
     *
     * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
     */
    public function modInverse(BCMath $n): ?BCMath
    {
        return $this->modInverseHelper($n);
    }

    /**
     * Calculates the greatest common divisor and Bezout's identity.
     *
     * Say you have 693 and 609.  The GCD is 21.  Bezout's identity states that there exist integers x and y such that
     * 693*x + 609*y == 21.  In point of fact, there are actually an infinite number of x and y combinations and which
     * combination is returned is dependent upon which mode is in use.  See
     * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.
     *
     * @return array{gcd: static, x: static, y: static}
     */
    public function extendedGCD(BCMath $n): array
    {
        // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
        // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway.  as is,
        // the basic extended euclidean algorithim is what we're using.

        $u = $this->value;
        $v = $n->value;

        $a = '1';
        $b = '0';
        $c = '0';
        $d = '1';

        while (bccomp($v, '0', 0) != 0) {
            $q = bcdiv($u, $v, 0);

            $temp = $u;
            $u = $v;
            $v = bcsub($temp, bcmul($v, $q, 0), 0);

            $temp = $a;
            $a = $c;
            $c = bcsub($temp, bcmul($a, $q, 0), 0);

            $temp = $b;
            $b = $d;
            $d = bcsub($temp, bcmul($b, $q, 0), 0);
        }

        return [
            'gcd' => $this->normalize(new static($u)),
            'x' => $this->normalize(new static($a)),
            'y' => $this->normalize(new static($b)),
        ];
    }

    /**
     * Calculates the greatest common divisor
     *
     * Say you have 693 and 609.  The GCD is 21.
     */
    public function gcd(BCMath $n): static
    {
        ['gcd' => $gcd] = $this->extendedGCD($n);
        return $gcd;
    }

    /**
     * Absolute value.
     */
    public function abs(): static
    {
        $temp = new static();
        $temp->value = strlen($this->value) && $this->value[0] == '-' ?
            substr($this->value, 1) :
            $this->value;

        return $temp;
    }

    /**
     * Logical And
     */
    public function bitwise_and(BCMath $x): static
    {
        return $this->bitwiseAndHelper($x);
    }

    /**
     * Logical Or
     */
    public function bitwise_or(BCMath $x): static
    {
        return $this->bitwiseOrHelper($x);
    }

    /**
     * Logical Exclusive Or
     */
    public function bitwise_xor(BCMath $x): static
    {
        return $this->bitwiseXorHelper($x);
    }

    /**
     * Logical Right Shift
     *
     * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
     */
    public function bitwise_rightShift(int $shift): static
    {
        $temp = new static();
        $temp->value = bcdiv($this->value, bcpow('2', (string)$shift, 0), 0);

        return $this->normalize($temp);
    }

    /**
     * Logical Left Shift
     *
     * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
     */
    public function bitwise_leftShift(int $shift): static
    {
        $temp = new static();
        $temp->value = bcmul($this->value, bcpow('2', (string) $shift, 0), 0);

        return $this->normalize($temp);
    }

    /**
     * Compares two numbers.
     *
     * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite.  The reason for this
     * is demonstrated thusly:
     *
     * $x  > $y: $x->compare($y)  > 0
     * $x  < $y: $x->compare($y)  < 0
     * $x == $y: $x->compare($y) == 0
     *
     * Note how the same comparison operator is used.  If you want to test for equality, use $x->equals($y).
     *
     * {@internal Could return $this->subtract($x), but that's not as fast as what we do do.}
     *
     * @return int in case < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
     * @see self::equals()
     */
    public function compare(BCMath $y): int
    {
        return bccomp($this->value, $y->value, 0);
    }

    /**
     * Tests the equality of two numbers.
     *
     * If you need to see if one number is greater than or less than another number, use BigInteger::compare()
     */
    public function equals(BCMath $x): bool
    {
        return $this->value == $x->value;
    }

    /**
     * Performs modular exponentiation.
     */
    public function modPow(BCMath $e, BCMath $n): ?BCMath
    {
        return $this->powModOuter($e, $n);
    }

    /**
     * Performs modular exponentiation.
     *
     * Alias for modPow().
     */
    public function powMod(BCMath $e, BCMath $n): ?BCMath
    {
        return $this->powModOuter($e, $n);
    }

    /**
     * Performs modular exponentiation.
     */
    protected function powModInner(BCMath $e, BCMath $n): static
    {
        try {
            $class = static::$modexpEngine[static::class];
            return $class::powModHelper($this, $e, $n, static::class);
        } catch (\Exception) {
            return BCMath\DefaultEngine::powModHelper($this, $e, $n, static::class);
        }
    }

    /**
     * Normalize
     *
     * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
     */
    protected function normalize(BCMath $result): static
    {
        $result->precision = $this->precision;
        $result->bitmask = $this->bitmask;

        if (isset($result->bitmask)) {
            $result->value = bcmod($result->value, $result->bitmask->value, 0);
        }

        return $result;
    }

    /**
     * Generate a random prime number between a range
     *
     * If there's not a prime within the given range, null will be returned.
     */
    public static function randomRangePrime(BCMath $min, BCMath $max): ?BCMath
    {
        return self::randomRangePrimeOuter($min, $max);
    }

    /**
     * Generate a random number between a range
     *
     * Returns a random number between $min and $max where $min and $max
     * can be defined using one of the two methods:
     *
     * BigInteger::randomRange($min, $max)
     * BigInteger::randomRange($max, $min)
     */
    public static function randomRange(BCMath $min, BCMath $max): static
    {
        return self::randomRangeHelper($min, $max);
    }

    /**
     * Make the current number odd
     *
     * If the current number is odd it'll be unchanged.  If it's even, one will be added to it.
     *
     * @see self::randomPrime()
     */
    protected function make_odd(): void
    {
        if (!$this->isOdd()) {
            $this->value = bcadd($this->value, '1', 0);
        }
    }

    /**
     * Test the number against small primes.
     *
     * @see self::isPrime()
     */
    protected function testSmallPrimes(): bool
    {
        if ($this->value === '1') {
            return false;
        }
        if ($this->value === '2') {
            return true;
        }
        if ($this->value[-1] % 2 == 0) {
            return false;
        }

        foreach (self::PRIMES as $prime) {
            $r = bcmod($this->value, (string) $prime, 0);
            if ($r == '0') {
                return $this->value == $prime;
            }
        }

        return true;
    }

    /**
     * Scan for 1 and right shift by that amount
     *
     * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
     *
     * @see self::isPrime()
     */
    public static function scan1divide(BCMath $r): int
    {
        $r_value = &$r->value;
        $s = 0;
        // 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
        while ($r_value[-1] % 2 == 0) {
            $r_value = bcdiv($r_value, '2', 0);
            ++$s;
        }

        return $s;
    }

    /**
     * Performs exponentiation.
     */
    public function pow(BCMath $n): static
    {
        $temp = new static();
        $temp->value = bcpow($this->value, $n->value, 0);

        return $this->normalize($temp);
    }

    /**
     * Return the minimum BigInteger between an arbitrary number of BigIntegers.
     */
    public static function min(BCMath ...$nums): static
    {
        return self::minHelper($nums);
    }

    /**
     * Return the maximum BigInteger between an arbitrary number of BigIntegers.
     */
    public static function max(BCMath ...$nums): static
    {
        return self::maxHelper($nums);
    }

    /**
     * Tests BigInteger to see if it is between two integers, inclusive
     */
    public function between(BCMath $min, BCMath $max): bool
    {
        return $this->compare($min) >= 0 && $this->compare($max) <= 0;
    }

    /**
     * Set Bitmask
     *
     * @see self::setPrecision()
     */
    protected static function setBitmask(int $bits): static
    {
        $temp = parent::setBitmask($bits);
        return $temp->add(static::$one[static::class]);
    }

    /**
     * Is Odd?
     */
    public function isOdd(): bool
    {
        return $this->value[-1] % 2 == 1;
    }

    /**
     * Tests if a bit is set
     */
    public function testBit($x): bool
    {
        $divisor = bcpow('2', (string) ($x + 1), 0);
        return bccomp(
            bcmod($this->value, $divisor, 0),
            bcpow('2', "$x", 0),
            0
        ) >= 0;
    }

    /**
     * Is Negative?
     */
    public function isNegative(): bool
    {
        return strlen($this->value) && $this->value[0] == '-';
    }

    /**
     * Negate
     *
     * Given $k, returns -$k
     */
    public function negate(): static
    {
        $temp = clone $this;

        if (!strlen($temp->value)) {
            return $temp;
        }

        $temp->value = $temp->value[0] == '-' ?
            substr($this->value, 1) :
            '-' . $this->value;

        return $temp;
    }
}