<?php
// =============================================================
// BigInt — минимальный беззнаковый big-integer на чистом PHP.
// =============================================================
// Назначение: модульная арифметика для secp256k1 / EIP-712 на хостингах
// без ext-gmp и ext-bcmath. Числа хранятся как little-endian массив
// 16-битных «лимбов» (0..65535). Все значения НЕОТРИЦАТЕЛЬНЫЕ — знак не
// нужен, т.к. вся арифметика модульная и инверсия считается через
// Малую теорему Ферма (modpow), а не расширенный Евклид.
//
// Производительность: для копи-бота (единицы подписей за cron-тик) этого
// достаточно. Интерфейс намеренно узкий, чтобы при наличии ext-gmp можно
// было подменить backend без переписывания вызывающего кода.
//
// Внутреннее представление ($limbs): массив int, индекс 0 = младшие 16 бит.
// Канонично: без ведущих нулевых лимбов; ноль = [] (пустой массив).

namespace HL\Crypto;

final class BigInt
{
    private const SHIFT = 16;
    private const BASE  = 65536;      // 2^16
    private const MASK  = 0xFFFF;

    /** @var int[] little-endian base-2^16 limbs */
    private array $limbs;

    private function __construct(array $limbs)
    {
        $this->limbs = self::trim($limbs);
    }

    // --------------------------------------------------------- конструкторы

    public static function zero(): self
    {
        return new self([]);
    }

    public static function fromInt(int $n): self
    {
        if ($n < 0) {
            throw new \InvalidArgumentException('BigInt: отрицательные числа не поддерживаются');
        }
        $limbs = [];
        while ($n > 0) {
            $limbs[] = $n & self::MASK;
            $n >>= self::SHIFT;
        }
        return new self($limbs);
    }

    /** Из hex-строки (с/без 0x, любая длина, регистр любой). */
    public static function fromHex(string $hex): self
    {
        $hex = strtolower($hex);
        if (str_starts_with($hex, '0x')) {
            $hex = substr($hex, 2);
        }
        $hex = ltrim($hex, '0');
        if ($hex === '') {
            return self::zero();
        }
        $limbs = [];
        // по 4 hex-символа = 16 бит, с конца
        for ($i = strlen($hex); $i > 0; $i -= 4) {
            $start = max(0, $i - 4);
            $limbs[] = (int) hexdec(substr($hex, $start, $i - $start));
        }
        return new self($limbs);
    }

    /** Из бинарной строки big-endian (как 32-байтовый дайджест). */
    public static function fromBytesBE(string $bin): self
    {
        if ($bin === '') {
            return self::zero();
        }
        // паддим слева до кратности 2 байт
        if (strlen($bin) % 2 === 1) {
            $bin = "\x00" . $bin;
        }
        $limbs = [];
        for ($i = strlen($bin); $i > 0; $i -= 2) {
            $hi = ord($bin[$i - 2]);
            $lo = ord($bin[$i - 1]);
            $limbs[] = ($hi << 8) | $lo;
        }
        return new self($limbs);
    }

    // ----------------------------------------------------------- экспортеры

    public function isZero(): bool
    {
        return $this->limbs === [];
    }

    public function isEven(): bool
    {
        return $this->limbs === [] || ($this->limbs[0] & 1) === 0;
    }

    public function toHex(): string
    {
        if ($this->limbs === []) {
            return '0';
        }
        $n = count($this->limbs);
        $out = dechex($this->limbs[$n - 1]);
        for ($i = $n - 2; $i >= 0; $i--) {
            $out .= str_pad(dechex($this->limbs[$i]), 4, '0', STR_PAD_LEFT);
        }
        return $out;
    }

    /** Big-endian бинарная строка ровно $len байт (паддинг нулями слева). */
    public function toBytesBE(int $len): string
    {
        $hex = $this->toHex();
        if ($hex === '0') {
            $hex = '';
        }
        $hex = str_pad($hex, $len * 2, '0', STR_PAD_LEFT);
        if (strlen($hex) > $len * 2) {
            throw new \RuntimeException('BigInt: значение не помещается в ' . $len . ' байт');
        }
        return hex2bin($hex);
    }

    public function toInt(): int
    {
        $r = 0;
        for ($i = count($this->limbs) - 1; $i >= 0; $i--) {
            $r = ($r << self::SHIFT) | $this->limbs[$i];
        }
        return $r;
    }

    // ------------------------------------------------------------- сравнение

    public function cmp(self $b): int
    {
        return self::cmpLimbs($this->limbs, $b->limbs);
    }

    public function equals(self $b): bool
    {
        return $this->limbs === $b->limbs;
    }

    private static function cmpLimbs(array $a, array $b): int
    {
        $na = count($a);
        $nb = count($b);
        if ($na !== $nb) {
            return $na <=> $nb;
        }
        for ($i = $na - 1; $i >= 0; $i--) {
            if ($a[$i] !== $b[$i]) {
                return $a[$i] <=> $b[$i];
            }
        }
        return 0;
    }

    // ------------------------------------------------------------- арифметика

    public function add(self $b): self
    {
        return new self(self::addLimbs($this->limbs, $b->limbs));
    }

    /** $this - $b, требует $this >= $b. */
    public function sub(self $b): self
    {
        return new self(self::subLimbs($this->limbs, $b->limbs));
    }

    public function mul(self $b): self
    {
        return new self(self::mulLimbs($this->limbs, $b->limbs));
    }

    /** Битовая длина. */
    public function bitLength(): int
    {
        $n = count($this->limbs);
        if ($n === 0) {
            return 0;
        }
        $top = $this->limbs[$n - 1];
        $bits = 0;
        while ($top > 0) {
            $bits++;
            $top >>= 1;
        }
        return ($n - 1) * self::SHIFT + $bits;
    }

    // ------------------------------------------------------- модульная арифм.

    public function mod(self $m): self
    {
        return new self(self::modLimbs($this->limbs, $m->limbs));
    }

    public function addMod(self $b, self $m): self
    {
        $s = self::addLimbs($this->limbs, $b->limbs);
        if (self::cmpLimbs($s, $m->limbs) >= 0) {
            $s = self::subLimbs($s, $m->limbs);
        }
        return new self(self::cmpLimbs($s, $m->limbs) >= 0 ? self::modLimbs($s, $m->limbs) : $s);
    }

    public function subMod(self $b, self $m): self
    {
        $a = self::modLimbs($this->limbs, $m->limbs);
        $bb = self::modLimbs($b->limbs, $m->limbs);
        if (self::cmpLimbs($a, $bb) >= 0) {
            return new self(self::subLimbs($a, $bb));
        }
        // m - (b - a)
        $diff = self::subLimbs($bb, $a);
        return new self(self::subLimbs($m->limbs, $diff));
    }

    public function mulMod(self $b, self $m): self
    {
        $p = self::mulLimbs($this->limbs, $b->limbs);
        return new self(self::modLimbs($p, $m->limbs));
    }

    /** Модульное возведение в степень (square-and-multiply). */
    public function powMod(self $e, self $m): self
    {
        if ($m->isZero()) {
            throw new \InvalidArgumentException('powMod: модуль 0');
        }
        $result = [1];
        $base = self::modLimbs($this->limbs, $m->limbs);
        $exp = $e->limbs;
        $mm = $m->limbs;
        $nbits = (new self($exp))->bitLength();
        for ($i = 0; $i < $nbits; $i++) {
            $limbIdx = intdiv($i, self::SHIFT);
            $bit = ($exp[$limbIdx] >> ($i % self::SHIFT)) & 1;
            if ($bit) {
                $result = self::modLimbs(self::mulLimbs($result, $base), $mm);
            }
            $base = self::modLimbs(self::mulLimbs($base, $base), $mm);
        }
        return new self($result);
    }

    /** Модульная инверсия через Ферма: a^(m-2) mod m (m — простое). */
    public function invMod(self $m): self
    {
        $mMinus2 = self::subLimbs($m->limbs, [2]);
        return $this->powMod(new self($mMinus2), $m);
    }

    // ----------------------------------------------- низкоуровневые лимб-операции

    private static function trim(array $limbs): array
    {
        $n = count($limbs);
        while ($n > 0 && $limbs[$n - 1] === 0) {
            array_pop($limbs);
            $n--;
        }
        return $limbs;
    }

    private static function addLimbs(array $a, array $b): array
    {
        $na = count($a);
        $nb = count($b);
        $n = max($na, $nb);
        $out = [];
        $carry = 0;
        for ($i = 0; $i < $n; $i++) {
            $s = $carry + ($i < $na ? $a[$i] : 0) + ($i < $nb ? $b[$i] : 0);
            $out[$i] = $s & self::MASK;
            $carry = $s >> self::SHIFT;
        }
        if ($carry) {
            $out[$n] = $carry;
        }
        return self::trim($out);
    }

    /** a - b, требует a >= b. */
    private static function subLimbs(array $a, array $b): array
    {
        $na = count($a);
        $nb = count($b);
        $out = [];
        $borrow = 0;
        for ($i = 0; $i < $na; $i++) {
            $d = $a[$i] - $borrow - ($i < $nb ? $b[$i] : 0);
            if ($d < 0) {
                $d += self::BASE;
                $borrow = 1;
            } else {
                $borrow = 0;
            }
            $out[$i] = $d;
        }
        return self::trim($out);
    }

    private static function mulLimbs(array $a, array $b): array
    {
        $na = count($a);
        $nb = count($b);
        if ($na === 0 || $nb === 0) {
            return [];
        }
        $out = array_fill(0, $na + $nb, 0);
        for ($i = 0; $i < $na; $i++) {
            $ai = $a[$i];
            if ($ai === 0) {
                continue;
            }
            $carry = 0;
            for ($j = 0; $j < $nb; $j++) {
                $t = $out[$i + $j] + $ai * $b[$j] + $carry;
                $out[$i + $j] = $t & self::MASK;
                $carry = $t >> self::SHIFT;
            }
            $out[$i + $nb] += $carry;
        }
        return self::trim($out);
    }

    /** Сдвиг влево на 1 бит. */
    private static function shl1(array $a): array
    {
        $out = [];
        $carry = 0;
        foreach ($a as $limb) {
            $v = ($limb << 1) | $carry;
            $out[] = $v & self::MASK;
            $carry = $v >> self::SHIFT;
        }
        if ($carry) {
            $out[] = $carry;
        }
        return $out;
    }

    /** Сдвиг вправо на 1 бит. */
    private static function shr1(array $a): array
    {
        $n = count($a);
        $out = array_fill(0, $n, 0);
        $carry = 0;
        for ($i = $n - 1; $i >= 0; $i--) {
            $v = $a[$i] | ($carry << self::SHIFT);
            $out[$i] = $v >> 1;
            $carry = $v & 1;
        }
        return self::trim($out);
    }

    /** Сдвиг влево на k бит. */
    private static function shlBits(array $a, int $k): array
    {
        if ($a === [] || $k === 0) {
            return $a;
        }
        $limbShift = intdiv($k, self::SHIFT);
        $bitShift  = $k % self::SHIFT;
        $out = array_fill(0, $limbShift, 0);
        if ($bitShift === 0) {
            foreach ($a as $l) {
                $out[] = $l;
            }
            return self::trim($out);
        }
        $carry = 0;
        foreach ($a as $limb) {
            $v = ($limb << $bitShift) | $carry;
            $out[] = $v & self::MASK;
            $carry = $v >> self::SHIFT;
        }
        if ($carry) {
            $out[] = $carry;
        }
        return self::trim($out);
    }

    private static function bitLenLimbs(array $a): int
    {
        $n = count($a);
        if ($n === 0) {
            return 0;
        }
        $top = $a[$n - 1];
        $bits = 0;
        while ($top > 0) {
            $bits++;
            $top >>= 1;
        }
        return ($n - 1) * self::SHIFT + $bits;
    }

    /** a mod m через бинарное деление (вычитание сдвинутого модуля). */
    private static function modLimbs(array $a, array $m): array
    {
        if ($m === []) {
            throw new \InvalidArgumentException('mod: деление на ноль');
        }
        if (self::cmpLimbs($a, $m) < 0) {
            return $a;
        }
        $r = $a;
        $diff = self::bitLenLimbs($r) - self::bitLenLimbs($m);
        if ($diff < 0) {
            return $r;
        }
        $shifted = self::shlBits($m, $diff);
        for ($i = $diff; $i >= 0; $i--) {
            if (self::cmpLimbs($shifted, $r) <= 0) {
                $r = self::subLimbs($r, $shifted);
            }
            $shifted = self::shr1($shifted);
        }
        return $r;
    }
}
