<?php

/**
 * Pure-PHP arbitrary precision integer arithmetic library.
 *
 * Supports base-2, base-10, base-16, and base-256 numbers.  Uses the GMP or BCMath extensions, if available,
 * and an internal implementation, otherwise.
 *
 * PHP version 8.1+
 *
 * Here's an example of how to use this library:
 * <code>
 * <?php
 *    $a = new \phpseclib4\Math\BigInteger(2);
 *    $b = new \phpseclib4\Math\BigInteger(3);
 *
 *    $c = $a->add($b);
 *
 *    echo $c->toString(); // outputs 5
 * ?>
 * </code>
 *
 * @author    Jim Wigginton <terrafrost@php.net>
 * @copyright 2007-2026 Jim Wigginton
 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
 */

declare(strict_types=1);

namespace phpseclib4\Math;

use phpseclib4\Exception\BadConfigurationException;
use phpseclib4\Math\BigInteger\Engines\Engine;

/**
 * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
 * numbers.
 *
 * @author  Jim Wigginton <terrafrost@php.net>
 * @psalm-api
 */
class BigInteger implements \JsonSerializable
{
    /**
     * Main Engine
     *
     * @var class-string<Engine>
     */
    private static string $mainEngine;

    /**
     * Selected Engines
     *
     * @var list<string>
     */
    private static array $engines;

    /**
     * The actual BigInteger object
     */
    private Engine $value;

    /**
     * Sets engine type.
     *
     * Throws an exception if the type is invalid
     *
     * @param list<string> $modexps optional
     */
    public static function setEngine(string $main, array $modexps = ['DefaultEngine']): void
    {
        self::$engines = [];

        $fqmain = 'phpseclib4\\Math\\BigInteger\\Engines\\' . $main;
        if (!class_exists($fqmain) || !method_exists($fqmain, 'isValidEngine')) {
            throw new BadConfigurationException("$main is not a valid engine");
        }
        if (!$fqmain::isValidEngine()) {
            throw new BadConfigurationException("$main is not setup correctly on this system");
        }
        /** @var class-string<Engine> $fqmain */
        self::$mainEngine = $fqmain;

        $found = false;
        foreach ($modexps as $modexp) {
            try {
                $fqmain::setModExpEngine($modexp);
                $found = true;
                break;
            } catch (\Exception) {
            }
        }

        if (!$found) {
            throw new BadConfigurationException("No valid modular exponentiation engine found for $main");
        }

        self::$engines = [$main, $modexp];
    }

    /**
     * Returns the engine type
     *
     * @return string[]
     */
    public static function getEngine(): array
    {
        self::initialize_static_variables();

        return self::$engines;
    }

    /**
     * Initialize static variables
     */
    private static function initialize_static_variables(): void
    {
        if (!isset(self::$mainEngine)) {
            $engines = [
                ['GMP', ['DefaultEngine']],
                ['PHP64', ['OpenSSL']],
                ['BCMath64', ['OpenSSL']],
                ['BCMath', ['OpenSSL']],
                ['PHP32', ['OpenSSL']],
                ['PHP64', ['DefaultEngine']],
                ['PHP32', ['DefaultEngine']],
            ];
            // per https://phpseclib.com/docs/speed PHP 8.4.0+ _significantly_ sped up BCMath
            if (PHP_VERSION_ID >= 80400) {
                $engines[1][0] = 'BCMath64';
                $engines[2][0] = 'BCMath';
                $engines[3][0] = 'PHP64';
            }

            foreach ($engines as $engine) {
                try {
                    self::setEngine($engine[0], $engine[1]);
                    return;
                } catch (\Exception $e) {
                }
            }

            throw new BadConfigurationException('No valid BigInteger mode found. This is only possible when JIT is enabled on Windows and neither the GMP or BCMath extensions are available, so either disable JIT or install GMP / BCMath');
        }
    }

    /**
     * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.
     *
     * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
     * two's compliment.  The sole exception to this is -10, which is treated the same as 10 is.
     */
    public function __construct(string|int|Engine $x = 0, int $base = 10)
    {
        self::initialize_static_variables();

        if ($x instanceof self::$mainEngine) {
            $this->value = clone $x;
        } elseif ($x instanceof Engine) {
            $this->value = new self::$mainEngine("$x");
            $this->value->setPrecision($x->getPrecision());
        } else {
            $this->value = new self::$mainEngine($x, $base);
        }
    }

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

    /**
     *  __toString() magic method
     */
    public function __toString(): string
    {
        return (string) $this->value;
    }

    /**
     *  __debugInfo() magic method
     *
     * Will be called, automatically, when print_r() or var_dump() are called
     */
    public function __debugInfo(): array
    {
        return $this->value->__debugInfo();
    }

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

    /**
     * Converts a BigInteger to a hex string (eg. base-16).
     */
    public function toHex(bool $twos_compliment = false): string
    {
        return $this->value->toHex($twos_compliment);
    }

    /**
     * Converts a BigInteger to a bit string (eg. base-2).
     *
     * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
     * saved as two's compliment.
     */
    public function toBits(bool $twos_compliment = false): string
    {
        return $this->value->toBits($twos_compliment);
    }

    /**
     * Adds two BigIntegers.
     */
    public function add(BigInteger $y): BigInteger
    {
        return new static($this->value->add($y->value));
    }

    /**
     * Subtracts two BigIntegers.
     */
    public function subtract(BigInteger $y): BigInteger
    {
        return new static($this->value->subtract($y->value));
    }

    /**
     * Multiplies two BigIntegers
     */
    public function multiply(BigInteger $x): BigInteger
    {
        return new static($this->value->multiply($x->value));
    }

    /**
     * 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).
     *
     * Here's an example:
     * <code>
     * <?php
     *    $a = new \phpseclib4\Math\BigInteger('10');
     *    $b = new \phpseclib4\Math\BigInteger('20');
     *
     *    [$quotient, $remainder] = $a->divide($b);
     *
     *    echo $quotient->toString(); // outputs 0
     *    echo "\r\n";
     *    echo $remainder->toString(); // outputs 10
     * ?>
     * </code>
     *
     * @return BigInteger[]
     */
    public function divide(BigInteger $y): array
    {
        [$q, $r] = $this->value->divide($y->value);
        return [
            new static($q),
            new static($r),
        ];
    }

    /**
     * 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(BigInteger $n): ?BigInteger
    {
        $value = $this->value->modInverse($n->value);
        return $value ? new static($value) : null;
    }

    /**
     * Calculates modular inverses.
     *
     * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
     *
     * @return BigInteger[]
     */
    public function extendedGCD(BigInteger $n): array
    {
        ['gcd' => $gcd, 'x' => $x, 'y' => $y] = $this->value->extendedGCD($n->value);
        return [
            'gcd' => new static($gcd),
            'x' => new static($x),
            'y' => new static($y),
        ];
    }

    /**
     * Calculates the greatest common divisor
     *
     * Say you have 693 and 609.  The GCD is 21.
     */
    public function gcd(BigInteger $n): BigInteger
    {
        return new static($this->value->gcd($n->value));
    }

    /**
     * Absolute value.
     */
    public function abs(): BigInteger
    {
        return new static($this->value->abs());
    }

    /**
     * Set Precision
     *
     * Some bitwise operations give different results depending on the precision being used.  Examples include left
     * shift, not, and rotates.
     */
    public function setPrecision(int $bits): void
    {
        $this->value->setPrecision($bits);
    }

    /**
     * Get Precision
     *
     * Returns the precision if it exists, -1 if it doesn't
     */
    public function getPrecision(): int
    {
        return $this->value->getPrecision();
    }

    /**
     *  __serialize() magic method
     *
     * @see self::__unserialize()
     */
    public function __serialize(): array
    {
        $result = ['hex' => $this->toHex(true)];
        if ($this->getPrecision() > 0) {
            $result['precision'] = $this->getPrecision();
        }
        return $result;
    }

    /**
     *  __unserialize() magic method
     *
     * @see self::__serialize()
     */
    public function __unserialize(array $data): void
    {
        $temp = new static($data['hex'], -16);
        $this->value = $temp->value;
        if (isset($data['precision']) && $data['precision'] > 0) {
            // recalculate $this->bitmask
            $this->setPrecision($data['precision']);
        }
    }

    /**
     * JSON Serialize
     *
     * Will be called, automatically, when json_encode() is called on a BigInteger object.
     *
     * @return array{hex: string, precision?: int]
     */
    public function jsonSerialize(): mixed
    {
        $result = ['hex' => $this->toHex(true)];
        if ($this->getPrecision() > 0) {
            $result['precision'] = $this->getPrecision();
        }
        return $result;
    }

    /**
     * Performs modular exponentiation.
     */
    public function powMod(BigInteger $e, BigInteger $n): BigInteger
    {
        return new static($this->value->powMod($e->value, $n->value));
    }

    /**
     * Performs modular exponentiation.
     */
    public function modPow(BigInteger $e, BigInteger $n): BigInteger
    {
        return new static($this->value->modPow($e->value, $n->value));
    }

    /**
     * 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(BigInteger $y): int
    {
        return $this->value->compare($y->value);
    }

    /**
     * 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(BigInteger $x): bool
    {
        return $this->value->equals($x->value);
    }

    /**
     * Logical Not
     */
    public function bitwise_not(): BigInteger
    {
        return new static($this->value->bitwise_not());
    }

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

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

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

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

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

    /**
     * Logical Left Rotate
     *
     * Instead of the top x bits being dropped they're appended to the shifted bit string.
     */
    public function bitwise_leftRotate(int $shift): BigInteger
    {
        return new static($this->value->bitwise_leftRotate($shift));
    }

    /**
     * Logical Right Rotate
     *
     * Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
     */
    public function bitwise_rightRotate(int $shift): BigInteger
    {
        return new static($this->value->bitwise_rightRotate($shift));
    }

    /**
     * Returns the smallest and largest n-bit number
     *
     * @return BigInteger[]
     */
    public static function minMaxBits(int $bits): array
    {
        self::initialize_static_variables();

        $class = self::$mainEngine;
        ['min' => $min, 'max' => $max] = $class::minMaxBits($bits);
        return [
            'min' => new static($min),
            'max' => new static($max),
        ];
    }

    /**
     * Return the size of a BigInteger in bits
     */
    public function getLength(): int
    {
        return $this->value->getLength();
    }

    /**
     * Return the size of a BigInteger in bytes
     */
    public function getLengthInBytes(): int
    {
        return $this->value->getLengthInBytes();
    }

    /**
     * Generates a random number of a certain size
     *
     * Bit length is equal to $size
     */
    public static function random(int $size): BigInteger
    {
        self::initialize_static_variables();

        $class = self::$mainEngine;
        return new static($class::random($size));
    }

    /**
     * Generates a random prime number of a certain size
     *
     * Bit length is equal to $size
     */
    public static function randomPrime(int $size): BigInteger
    {
        self::initialize_static_variables();

        $class = self::$mainEngine;
        return new static($class::randomPrime($size));
    }

    /**
     * Generate a random prime number between a range
     *
     * If there's not a prime within the given range, false will be returned.
     */
    public static function randomRangePrime(BigInteger $min, BigInteger $max): ?BigInteger
    {
        $class = self::$mainEngine;
        $result = $class::randomRangePrime($min->value, $max->value);
        if ($result === null) {
            return null;
        }
        return new static($result);
    }

    /**
     * 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(BigInteger $min, BigInteger $max): BigInteger
    {
        $class = self::$mainEngine;
        return new static($class::randomRange($min->value, $max->value));
    }

    /**
     * Checks a numer to see if it's prime
     *
     * Assuming the $t parameter is not set, this function has an error rate of 2**-80.  The main motivation for the
     * $t parameter is distributability.  BigInteger::randomPrime() can be distributed across multiple pageloads
     * on a website instead of just one.
     */
    public function isPrime(?int $t = null): bool
    {
        return $this->value->isPrime($t);
    }

    /**
     * Calculates the nth root of a biginteger.
     *
     * Returns the nth root of a positive biginteger, where n defaults to 2
     */
    public function root(int $n = 2): BigInteger
    {
        return new static($this->value->root($n));
    }

    /**
     * Performs exponentiation.
     */
    public function pow(BigInteger $n): BigInteger
    {
        return new static($this->value->pow($n->value));
    }

    /**
     * Return the minimum BigInteger between an arbitrary number of BigIntegers.
     */
    public static function min(BigInteger ...$nums): BigInteger
    {
        $class = self::$mainEngine;
        $nums = array_map(fn ($num) => $num->value, $nums);
        return new static($class::min(...$nums));
    }

    /**
     * Return the maximum BigInteger between an arbitrary number of BigIntegers.
     */
    public static function max(BigInteger ...$nums): BigInteger
    {
        $class = self::$mainEngine;
        $nums = array_map(fn ($num) => $num->value, $nums);
        return new static($class::max(...$nums));
    }

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

    /**
     * Clone
     */
    public function __clone()
    {
        $this->value = clone $this->value;
    }

    /**
     * Is Odd?
     */
    public function isOdd(): bool
    {
        return $this->value->isOdd();
    }

    /**
     * Tests if a bit is set
     */
    public function testBit(int $x): bool
    {
        return $this->value->testBit($x);
    }

    /**
     * Is Negative?
     */
    public function isNegative(): bool
    {
        return $this->value->isNegative();
    }

    /**
     * Negate
     *
     * Given $k, returns -$k
     */
    public function negate(): BigInteger
    {
        return new static($this->value->negate());
    }

    /**
     * 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));
     */
    public static function scan1divide(BigInteger $r): int
    {
        $class = self::$mainEngine;
        return $class::scan1divide($r->value);
    }

    /**
     * Create Recurring Modulo Function
     *
     * Sometimes it may be desirable to do repeated modulos with the same number outside of
     * modular exponentiation
     */
    public function createRecurringModuloFunction(): \Closure
    {
        $func = $this->value->createRecurringModuloFunction();
        return fn (BigInteger $x) => new static($func($x->value));
    }

    /**
     * Bitwise Split
     *
     * Splits BigInteger's into chunks of $split bits
     *
     * @return BigInteger[]
     */
    public function bitwise_split(int $split): array
    {
        return array_map(fn ($val) => new static($val), $this->value->bitwise_split($split));
    }
}