Subversion Repositories oidplus

Rev

Rev 1411 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. <?php
  2.  
  3. /**
  4.  * Pure-PHP BigInteger Engine
  5.  *
  6.  * PHP version 5 and 7
  7.  *
  8.  * @author    Jim Wigginton <terrafrost@php.net>
  9.  * @copyright 2017 Jim Wigginton
  10.  * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  11.  * @link      http://pear.php.net/package/Math_BigInteger
  12.  */
  13.  
  14. namespace phpseclib3\Math\BigInteger\Engines;
  15.  
  16. use phpseclib3\Common\Functions\Strings;
  17. use phpseclib3\Exception\BadConfigurationException;
  18.  
  19. /**
  20.  * Pure-PHP Engine.
  21.  *
  22.  * @author  Jim Wigginton <terrafrost@php.net>
  23.  */
  24. abstract class PHP extends Engine
  25. {
  26.     /**#@+
  27.      * Array constants
  28.      *
  29.      * Rather than create a thousands and thousands of new BigInteger objects in repeated function calls to add() and
  30.      * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them.
  31.      *
  32.      */
  33.     /**
  34.      * $result[self::VALUE] contains the value.
  35.      */
  36.     const VALUE = 0;
  37.     /**
  38.      * $result[self::SIGN] contains the sign.
  39.      */
  40.     const SIGN = 1;
  41.     /**#@-*/
  42.  
  43.     /**
  44.      * Karatsuba Cutoff
  45.      *
  46.      * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
  47.      *
  48.      */
  49.     const KARATSUBA_CUTOFF = 25;
  50.  
  51.     /**
  52.      * Can Bitwise operations be done fast?
  53.      *
  54.      * @see parent::bitwise_leftRotate()
  55.      * @see parent::bitwise_rightRotate()
  56.      */
  57.     const FAST_BITWISE = true;
  58.  
  59.     /**
  60.      * Engine Directory
  61.      *
  62.      * @see parent::setModExpEngine
  63.      */
  64.     const ENGINE_DIR = 'PHP';
  65.  
  66.     /**
  67.      * Default constructor
  68.      *
  69.      * @param mixed $x integer Base-10 number or base-$base number if $base set.
  70.      * @param int $base
  71.      * @return PHP
  72.      * @see parent::__construct()
  73.      */
  74.     public function __construct($x = 0, $base = 10)
  75.     {
  76.         if (!isset(static::$isValidEngine[static::class])) {
  77.             static::$isValidEngine[static::class] = static::isValidEngine();
  78.         }
  79.         if (!static::$isValidEngine[static::class]) {
  80.             throw new BadConfigurationException(static::class . ' is not setup correctly on this system');
  81.         }
  82.  
  83.         $this->value = [];
  84.         parent::__construct($x, $base);
  85.     }
  86.  
  87.     /**
  88.      * Initialize a PHP BigInteger Engine instance
  89.      *
  90.      * @param int $base
  91.      * @see parent::__construct()
  92.      */
  93.     protected function initialize($base)
  94.     {
  95.         switch (abs($base)) {
  96.             case 16:
  97.                 $x = (strlen($this->value) & 1) ? '0' . $this->value : $this->value;
  98.                 $temp = new static(Strings::hex2bin($x), 256);
  99.                 $this->value = $temp->value;
  100.                 break;
  101.             case 10:
  102.                 $temp = new static();
  103.  
  104.                 $multiplier = new static();
  105.                 $multiplier->value = [static::MAX10];
  106.  
  107.                 $x = $this->value;
  108.  
  109.                 if ($x[0] == '-') {
  110.                     $this->is_negative = true;
  111.                     $x = substr($x, 1);
  112.                 }
  113.  
  114.                 $x = str_pad(
  115.                     $x,
  116.                     strlen($x) + ((static::MAX10LEN - 1) * strlen($x)) % static::MAX10LEN,
  117.                     0,
  118.                     STR_PAD_LEFT
  119.                 );
  120.                 while (strlen($x)) {
  121.                     $temp = $temp->multiply($multiplier);
  122.                     $temp = $temp->add(new static($this->int2bytes(substr($x, 0, static::MAX10LEN)), 256));
  123.                     $x = substr($x, static::MAX10LEN);
  124.                 }
  125.  
  126.                 $this->value = $temp->value;
  127.         }
  128.     }
  129.  
  130.     /**
  131.      * Pads strings so that unpack may be used on them
  132.      *
  133.      * @param string $str
  134.      * @return string
  135.      */
  136.     protected function pad($str)
  137.     {
  138.         $length = strlen($str);
  139.  
  140.         $pad = 4 - (strlen($str) % 4);
  141.  
  142.         return str_pad($str, $length + $pad, "\0", STR_PAD_LEFT);
  143.     }
  144.  
  145.     /**
  146.      * Converts a BigInteger to a base-10 number.
  147.      *
  148.      * @return string
  149.      */
  150.     public function toString()
  151.     {
  152.         if (!count($this->value)) {
  153.             return '0';
  154.         }
  155.  
  156.         $temp = clone $this;
  157.         $temp->bitmask = false;
  158.         $temp->is_negative = false;
  159.  
  160.         $divisor = new static();
  161.         $divisor->value = [static::MAX10];
  162.         $result = '';
  163.         while (count($temp->value)) {
  164.             list($temp, $mod) = $temp->divide($divisor);
  165.             $result = str_pad(
  166.                 isset($mod->value[0]) ? $mod->value[0] : '',
  167.                 static::MAX10LEN,
  168.                 '0',
  169.                 STR_PAD_LEFT
  170.             ) . $result;
  171.         }
  172.         $result = ltrim($result, '0');
  173.         if (empty($result)) {
  174.             $result = '0';
  175.         }
  176.  
  177.         if ($this->is_negative) {
  178.             $result = '-' . $result;
  179.         }
  180.  
  181.         return $result;
  182.     }
  183.  
  184.     /**
  185.      * Converts a BigInteger to a byte string (eg. base-256).
  186.      *
  187.      * @param bool $twos_compliment
  188.      * @return string
  189.      */
  190.     public function toBytes($twos_compliment = false)
  191.     {
  192.         if ($twos_compliment) {
  193.             return $this->toBytesHelper();
  194.         }
  195.  
  196.         if (!count($this->value)) {
  197.             return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
  198.         }
  199.  
  200.         $result = $this->bitwise_small_split(8);
  201.         $result = implode('', array_map('chr', $result));
  202.  
  203.         return $this->precision > 0 ?
  204.             str_pad(
  205.                 substr($result, -(($this->precision + 7) >> 3)),
  206.                 ($this->precision + 7) >> 3,
  207.                 chr(0),
  208.                 STR_PAD_LEFT
  209.             ) :
  210.             $result;
  211.     }
  212.  
  213.     /**
  214.      * Performs addition.
  215.      *
  216.      * @param array $x_value
  217.      * @param bool $x_negative
  218.      * @param array $y_value
  219.      * @param bool $y_negative
  220.      * @return array
  221.      */
  222.     protected static function addHelper(array $x_value, $x_negative, array $y_value, $y_negative)
  223.     {
  224.         $x_size = count($x_value);
  225.         $y_size = count($y_value);
  226.  
  227.         if ($x_size == 0) {
  228.             return [
  229.                 self::VALUE => $y_value,
  230.                 self::SIGN => $y_negative
  231.             ];
  232.         } elseif ($y_size == 0) {
  233.             return [
  234.                 self::VALUE => $x_value,
  235.                 self::SIGN => $x_negative
  236.             ];
  237.         }
  238.  
  239.         // subtract, if appropriate
  240.         if ($x_negative != $y_negative) {
  241.             if ($x_value == $y_value) {
  242.                 return [
  243.                     self::VALUE => [],
  244.                     self::SIGN => false
  245.                 ];
  246.             }
  247.  
  248.             $temp = self::subtractHelper($x_value, false, $y_value, false);
  249.             $temp[self::SIGN] = self::compareHelper($x_value, false, $y_value, false) > 0 ?
  250.                 $x_negative : $y_negative;
  251.  
  252.             return $temp;
  253.         }
  254.  
  255.         if ($x_size < $y_size) {
  256.             $size = $x_size;
  257.             $value = $y_value;
  258.         } else {
  259.             $size = $y_size;
  260.             $value = $x_value;
  261.         }
  262.  
  263.         $value[count($value)] = 0; // just in case the carry adds an extra digit
  264.  
  265.         $carry = 0;
  266.         for ($i = 0, $j = 1; $j < $size; $i += 2, $j += 2) {
  267.             //$sum = $x_value[$j] * static::BASE_FULL + $x_value[$i] + $y_value[$j] * static::BASE_FULL + $y_value[$i] + $carry;
  268.             $sum = ($x_value[$j] + $y_value[$j]) * static::BASE_FULL + $x_value[$i] + $y_value[$i] + $carry;
  269.             $carry = $sum >= static::MAX_DIGIT2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
  270.             $sum = $carry ? $sum - static::MAX_DIGIT2 : $sum;
  271.  
  272.             $temp = static::BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
  273.  
  274.             $value[$i] = (int)($sum - static::BASE_FULL * $temp); // eg. a faster alternative to fmod($sum, 0x4000000)
  275.             $value[$j] = $temp;
  276.         }
  277.  
  278.         if ($j == $size) { // ie. if $y_size is odd
  279.             $sum = $x_value[$i] + $y_value[$i] + $carry;
  280.             $carry = $sum >= static::BASE_FULL;
  281.             $value[$i] = $carry ? $sum - static::BASE_FULL : $sum;
  282.             ++$i; // ie. let $i = $j since we've just done $value[$i]
  283.         }
  284.  
  285.         if ($carry) {
  286.             for (; $value[$i] == static::MAX_DIGIT; ++$i) {
  287.                 $value[$i] = 0;
  288.             }
  289.             ++$value[$i];
  290.         }
  291.  
  292.         return [
  293.             self::VALUE => self::trim($value),
  294.             self::SIGN => $x_negative
  295.         ];
  296.     }
  297.  
  298.     /**
  299.      * Performs subtraction.
  300.      *
  301.      * @param array $x_value
  302.      * @param bool $x_negative
  303.      * @param array $y_value
  304.      * @param bool $y_negative
  305.      * @return array
  306.      */
  307.     public static function subtractHelper(array $x_value, $x_negative, array $y_value, $y_negative)
  308.     {
  309.         $x_size = count($x_value);
  310.         $y_size = count($y_value);
  311.  
  312.         if ($x_size == 0) {
  313.             return [
  314.                 self::VALUE => $y_value,
  315.                 self::SIGN => !$y_negative
  316.             ];
  317.         } elseif ($y_size == 0) {
  318.             return [
  319.                 self::VALUE => $x_value,
  320.                 self::SIGN => $x_negative
  321.             ];
  322.         }
  323.  
  324.         // add, if appropriate (ie. -$x - +$y or +$x - -$y)
  325.         if ($x_negative != $y_negative) {
  326.             $temp = self::addHelper($x_value, false, $y_value, false);
  327.             $temp[self::SIGN] = $x_negative;
  328.  
  329.             return $temp;
  330.         }
  331.  
  332.         $diff = self::compareHelper($x_value, $x_negative, $y_value, $y_negative);
  333.  
  334.         if (!$diff) {
  335.             return [
  336.                 self::VALUE => [],
  337.                 self::SIGN => false
  338.             ];
  339.         }
  340.  
  341.         // switch $x and $y around, if appropriate.
  342.         if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) {
  343.             $temp = $x_value;
  344.             $x_value = $y_value;
  345.             $y_value = $temp;
  346.  
  347.             $x_negative = !$x_negative;
  348.  
  349.             $x_size = count($x_value);
  350.             $y_size = count($y_value);
  351.         }
  352.  
  353.         // at this point, $x_value should be at least as big as - if not bigger than - $y_value
  354.  
  355.         $carry = 0;
  356.         for ($i = 0, $j = 1; $j < $y_size; $i += 2, $j += 2) {
  357.             $sum = ($x_value[$j] - $y_value[$j]) * static::BASE_FULL + $x_value[$i] - $y_value[$i] - $carry;
  358.  
  359.             $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
  360.             $sum = $carry ? $sum + static::MAX_DIGIT2 : $sum;
  361.  
  362.             $temp = static::BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
  363.  
  364.             $x_value[$i] = (int)($sum - static::BASE_FULL * $temp);
  365.             $x_value[$j] = $temp;
  366.         }
  367.  
  368.         if ($j == $y_size) { // ie. if $y_size is odd
  369.             $sum = $x_value[$i] - $y_value[$i] - $carry;
  370.             $carry = $sum < 0;
  371.             $x_value[$i] = $carry ? $sum + static::BASE_FULL : $sum;
  372.             ++$i;
  373.         }
  374.  
  375.         if ($carry) {
  376.             for (; !$x_value[$i]; ++$i) {
  377.                 $x_value[$i] = static::MAX_DIGIT;
  378.             }
  379.             --$x_value[$i];
  380.         }
  381.  
  382.         return [
  383.             self::VALUE => self::trim($x_value),
  384.             self::SIGN => $x_negative
  385.         ];
  386.     }
  387.  
  388.     /**
  389.      * Performs multiplication.
  390.      *
  391.      * @param array $x_value
  392.      * @param bool $x_negative
  393.      * @param array $y_value
  394.      * @param bool $y_negative
  395.      * @return array
  396.      */
  397.     protected static function multiplyHelper(array $x_value, $x_negative, array $y_value, $y_negative)
  398.     {
  399.         //if ( $x_value == $y_value ) {
  400.         //    return [
  401.         //        self::VALUE => self::square($x_value),
  402.         //        self::SIGN => $x_sign != $y_value
  403.         //    ];
  404.         //}
  405.  
  406.         $x_length = count($x_value);
  407.         $y_length = count($y_value);
  408.  
  409.         if (!$x_length || !$y_length) { // a 0 is being multiplied
  410.             return [
  411.                 self::VALUE => [],
  412.                 self::SIGN => false
  413.             ];
  414.         }
  415.  
  416.         return [
  417.             self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ?
  418.                 self::trim(self::regularMultiply($x_value, $y_value)) :
  419.                 self::trim(self::karatsuba($x_value, $y_value)),
  420.             self::SIGN => $x_negative != $y_negative
  421.         ];
  422.     }
  423.  
  424.     /**
  425.      * Performs Karatsuba multiplication on two BigIntegers
  426.      *
  427.      * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
  428.      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.
  429.      *
  430.      * @param array $x_value
  431.      * @param array $y_value
  432.      * @return array
  433.      */
  434.     private static function karatsuba(array $x_value, array $y_value)
  435.     {
  436.         $m = min(count($x_value) >> 1, count($y_value) >> 1);
  437.  
  438.         if ($m < self::KARATSUBA_CUTOFF) {
  439.             return self::regularMultiply($x_value, $y_value);
  440.         }
  441.  
  442.         $x1 = array_slice($x_value, $m);
  443.         $x0 = array_slice($x_value, 0, $m);
  444.         $y1 = array_slice($y_value, $m);
  445.         $y0 = array_slice($y_value, 0, $m);
  446.  
  447.         $z2 = self::karatsuba($x1, $y1);
  448.         $z0 = self::karatsuba($x0, $y0);
  449.  
  450.         $z1 = self::addHelper($x1, false, $x0, false);
  451.         $temp = self::addHelper($y1, false, $y0, false);
  452.         $z1 = self::karatsuba($z1[self::VALUE], $temp[self::VALUE]);
  453.         $temp = self::addHelper($z2, false, $z0, false);
  454.         $z1 = self::subtractHelper($z1, false, $temp[self::VALUE], false);
  455.  
  456.         $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
  457.         $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]);
  458.  
  459.         $xy = self::addHelper($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
  460.         $xy = self::addHelper($xy[self::VALUE], $xy[self::SIGN], $z0, false);
  461.  
  462.         return $xy[self::VALUE];
  463.     }
  464.  
  465.     /**
  466.      * Performs long multiplication on two BigIntegers
  467.      *
  468.      * Modeled after 'multiply' in MutableBigInteger.java.
  469.      *
  470.      * @param array $x_value
  471.      * @param array $y_value
  472.      * @return array
  473.      */
  474.     protected static function regularMultiply(array $x_value, array $y_value)
  475.     {
  476.         $x_length = count($x_value);
  477.         $y_length = count($y_value);
  478.  
  479.         if (!$x_length || !$y_length) { // a 0 is being multiplied
  480.             return [];
  481.         }
  482.  
  483.         $product_value = self::array_repeat(0, $x_length + $y_length);
  484.  
  485.         // the following for loop could be removed if the for loop following it
  486.         // (the one with nested for loops) initially set $i to 0, but
  487.         // doing so would also make the result in one set of unnecessary adds,
  488.         // since on the outermost loops first pass, $product->value[$k] is going
  489.         // to always be 0
  490.  
  491.         $carry = 0;
  492.         for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0
  493.             $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
  494.             $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  495.             $product_value[$j] = (int)($temp - static::BASE_FULL * $carry);
  496.         }
  497.  
  498.         $product_value[$j] = $carry;
  499.  
  500.         // the above for loop is what the previous comment was talking about.  the
  501.         // following for loop is the "one with nested for loops"
  502.         for ($i = 1; $i < $y_length; ++$i) {
  503.             $carry = 0;
  504.  
  505.             for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) {
  506.                 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
  507.                 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  508.                 $product_value[$k] = (int)($temp - static::BASE_FULL * $carry);
  509.             }
  510.  
  511.             $product_value[$k] = $carry;
  512.         }
  513.  
  514.         return $product_value;
  515.     }
  516.  
  517.     /**
  518.      * Divides two BigIntegers.
  519.      *
  520.      * Returns an array whose first element contains the quotient and whose second element contains the
  521.      * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
  522.      * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
  523.      * and the divisor (basically, the "common residue" is the first positive modulo).
  524.      *
  525.      * @return array{static, static}
  526.      * @internal This function is based off of
  527.      *     {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}.
  528.      */
  529.     protected function divideHelper(PHP $y)
  530.     {
  531.         if (count($y->value) == 1) {
  532.             list($q, $r) = $this->divide_digit($this->value, $y->value[0]);
  533.             $quotient = new static();
  534.             $remainder = new static();
  535.             $quotient->value = $q;
  536.             $remainder->value = [$r];
  537.             $quotient->is_negative = $this->is_negative != $y->is_negative;
  538.             return [$this->normalize($quotient), $this->normalize($remainder)];
  539.         }
  540.  
  541.         $x = clone $this;
  542.         $y = clone $y;
  543.  
  544.         $x_sign = $x->is_negative;
  545.         $y_sign = $y->is_negative;
  546.  
  547.         $x->is_negative = $y->is_negative = false;
  548.  
  549.         $diff = $x->compare($y);
  550.  
  551.         if (!$diff) {
  552.             $temp = new static();
  553.             $temp->value = [1];
  554.             $temp->is_negative = $x_sign != $y_sign;
  555.             return [$this->normalize($temp), $this->normalize(static::$zero[static::class])];
  556.         }
  557.  
  558.         if ($diff < 0) {
  559.             // if $x is negative, "add" $y.
  560.             if ($x_sign) {
  561.                 $x = $y->subtract($x);
  562.             }
  563.             return [$this->normalize(static::$zero[static::class]), $this->normalize($x)];
  564.         }
  565.  
  566.         // normalize $x and $y as described in HAC 14.23 / 14.24
  567.         $msb = $y->value[count($y->value) - 1];
  568.         for ($shift = 0; !($msb & static::MSB); ++$shift) {
  569.             $msb <<= 1;
  570.         }
  571.         $x->lshift($shift);
  572.         $y->lshift($shift);
  573.         $y_value = &$y->value;
  574.  
  575.         $x_max = count($x->value) - 1;
  576.         $y_max = count($y->value) - 1;
  577.  
  578.         $quotient = new static();
  579.         $quotient_value = &$quotient->value;
  580.         $quotient_value = self::array_repeat(0, $x_max - $y_max + 1);
  581.  
  582.         static $temp, $lhs, $rhs;
  583.         if (!isset($temp)) {
  584.             $temp = new static();
  585.             $lhs = new static();
  586.             $rhs = new static();
  587.         }
  588.         if (static::class != get_class($temp)) {
  589.             $temp = new static();
  590.             $lhs = new static();
  591.             $rhs = new static();
  592.         }
  593.         $temp_value = &$temp->value;
  594.         $rhs_value =  &$rhs->value;
  595.  
  596.         // $temp = $y << ($x_max - $y_max-1) in base 2**26
  597.         $temp_value = array_merge(self::array_repeat(0, $x_max - $y_max), $y_value);
  598.  
  599.         while ($x->compare($temp) >= 0) {
  600.             // calculate the "common residue"
  601.             ++$quotient_value[$x_max - $y_max];
  602.             $x = $x->subtract($temp);
  603.             $x_max = count($x->value) - 1;
  604.         }
  605.  
  606.         for ($i = $x_max; $i >= $y_max + 1; --$i) {
  607.             $x_value = &$x->value;
  608.             $x_window = [
  609.                 isset($x_value[$i]) ? $x_value[$i] : 0,
  610.                 isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0,
  611.                 isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0
  612.             ];
  613.             $y_window = [
  614.                 $y_value[$y_max],
  615.                 ($y_max > 0) ? $y_value[$y_max - 1] : 0
  616.             ];
  617.  
  618.             $q_index = $i - $y_max - 1;
  619.             if ($x_window[0] == $y_window[0]) {
  620.                 $quotient_value[$q_index] = static::MAX_DIGIT;
  621.             } else {
  622.                 $quotient_value[$q_index] = self::safe_divide(
  623.                     $x_window[0] * static::BASE_FULL + $x_window[1],
  624.                     $y_window[0]
  625.                 );
  626.             }
  627.  
  628.             $temp_value = [$y_window[1], $y_window[0]];
  629.  
  630.             $lhs->value = [$quotient_value[$q_index]];
  631.             $lhs = $lhs->multiply($temp);
  632.  
  633.             $rhs_value = [$x_window[2], $x_window[1], $x_window[0]];
  634.  
  635.             while ($lhs->compare($rhs) > 0) {
  636.                 --$quotient_value[$q_index];
  637.  
  638.                 $lhs->value = [$quotient_value[$q_index]];
  639.                 $lhs = $lhs->multiply($temp);
  640.             }
  641.  
  642.             $adjust = self::array_repeat(0, $q_index);
  643.             $temp_value = [$quotient_value[$q_index]];
  644.             $temp = $temp->multiply($y);
  645.             $temp_value = &$temp->value;
  646.             if (count($temp_value)) {
  647.                 $temp_value = array_merge($adjust, $temp_value);
  648.             }
  649.  
  650.             $x = $x->subtract($temp);
  651.  
  652.             if ($x->compare(static::$zero[static::class]) < 0) {
  653.                 $temp_value = array_merge($adjust, $y_value);
  654.                 $x = $x->add($temp);
  655.  
  656.                 --$quotient_value[$q_index];
  657.             }
  658.  
  659.             $x_max = count($x_value) - 1;
  660.         }
  661.  
  662.         // unnormalize the remainder
  663.         $x->rshift($shift);
  664.  
  665.         $quotient->is_negative = $x_sign != $y_sign;
  666.  
  667.         // calculate the "common residue", if appropriate
  668.         if ($x_sign) {
  669.             $y->rshift($shift);
  670.             $x = $y->subtract($x);
  671.         }
  672.  
  673.         return [$this->normalize($quotient), $this->normalize($x)];
  674.     }
  675.  
  676.     /**
  677.      * Divides a BigInteger by a regular integer
  678.      *
  679.      * abc / x = a00 / x + b0 / x + c / x
  680.      *
  681.      * @param array $dividend
  682.      * @param int $divisor
  683.      * @return array
  684.      */
  685.     private static function divide_digit(array $dividend, $divisor)
  686.     {
  687.         $carry = 0;
  688.         $result = [];
  689.  
  690.         for ($i = count($dividend) - 1; $i >= 0; --$i) {
  691.             $temp = static::BASE_FULL * $carry + $dividend[$i];
  692.             $result[$i] = self::safe_divide($temp, $divisor);
  693.             $carry = (int)($temp - $divisor * $result[$i]);
  694.         }
  695.  
  696.         return [$result, $carry];
  697.     }
  698.  
  699.     /**
  700.      * Single digit division
  701.      *
  702.      * Even if int64 is being used the division operator will return a float64 value
  703.      * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't
  704.      * have the precision of int64 this is a problem so, when int64 is being used,
  705.      * we'll guarantee that the dividend is divisible by first subtracting the remainder.
  706.      *
  707.      * @param int $x
  708.      * @param int $y
  709.      * @return int
  710.      */
  711.     private static function safe_divide($x, $y)
  712.     {
  713.         if (static::BASE === 26) {
  714.             return (int)($x / $y);
  715.         }
  716.  
  717.         // static::BASE === 31
  718.         /** @var int */
  719.         return ($x - ($x % $y)) / $y;
  720.     }
  721.  
  722.     /**
  723.      * Convert an array / boolean to a PHP BigInteger object
  724.      *
  725.      * @param array $arr
  726.      * @return static
  727.      */
  728.     protected function convertToObj(array $arr)
  729.     {
  730.         $result = new static();
  731.         $result->value = $arr[self::VALUE];
  732.         $result->is_negative = $arr[self::SIGN];
  733.  
  734.         return $this->normalize($result);
  735.     }
  736.  
  737.     /**
  738.      * Normalize
  739.      *
  740.      * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
  741.      *
  742.      * @param PHP $result
  743.      * @return static
  744.      */
  745.     protected function normalize(PHP $result)
  746.     {
  747.         $result->precision = $this->precision;
  748.         $result->bitmask = $this->bitmask;
  749.  
  750.         $value = &$result->value;
  751.  
  752.         if (!count($value)) {
  753.             $result->is_negative = false;
  754.             return $result;
  755.         }
  756.  
  757.         $value = static::trim($value);
  758.  
  759.         if (!empty($result->bitmask->value)) {
  760.             $length = min(count($value), count($result->bitmask->value));
  761.             $value = array_slice($value, 0, $length);
  762.  
  763.             for ($i = 0; $i < $length; ++$i) {
  764.                 $value[$i] = $value[$i] & $result->bitmask->value[$i];
  765.             }
  766.  
  767.             $value = static::trim($value);
  768.         }
  769.  
  770.         return $result;
  771.     }
  772.  
  773.     /**
  774.      * Compares two numbers.
  775.      *
  776.      * @param array $x_value
  777.      * @param bool $x_negative
  778.      * @param array $y_value
  779.      * @param bool $y_negative
  780.      * @return int
  781.      * @see static::compare()
  782.      */
  783.     protected static function compareHelper(array $x_value, $x_negative, array $y_value, $y_negative)
  784.     {
  785.         if ($x_negative != $y_negative) {
  786.             return (!$x_negative && $y_negative) ? 1 : -1;
  787.         }
  788.  
  789.         $result = $x_negative ? -1 : 1;
  790.  
  791.         if (count($x_value) != count($y_value)) {
  792.             return (count($x_value) > count($y_value)) ? $result : -$result;
  793.         }
  794.         $size = max(count($x_value), count($y_value));
  795.  
  796.         $x_value = array_pad($x_value, $size, 0);
  797.         $y_value = array_pad($y_value, $size, 0);
  798.  
  799.         for ($i = count($x_value) - 1; $i >= 0; --$i) {
  800.             if ($x_value[$i] != $y_value[$i]) {
  801.                 return ($x_value[$i] > $y_value[$i]) ? $result : -$result;
  802.             }
  803.         }
  804.  
  805.         return 0;
  806.     }
  807.  
  808.     /**
  809.      * Absolute value.
  810.      *
  811.      * @return PHP
  812.      */
  813.     public function abs()
  814.     {
  815.         $temp = new static();
  816.         $temp->value = $this->value;
  817.  
  818.         return $temp;
  819.     }
  820.  
  821.     /**
  822.      * Trim
  823.      *
  824.      * Removes leading zeros
  825.      *
  826.      * @param list<static> $value
  827.      * @return list<static>
  828.      */
  829.     protected static function trim(array $value)
  830.     {
  831.         for ($i = count($value) - 1; $i >= 0; --$i) {
  832.             if ($value[$i]) {
  833.                 break;
  834.             }
  835.             unset($value[$i]);
  836.         }
  837.  
  838.         return $value;
  839.     }
  840.  
  841.     /**
  842.      * Logical Right Shift
  843.      *
  844.      * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
  845.      *
  846.      * @param int $shift
  847.      * @return PHP
  848.      */
  849.     public function bitwise_rightShift($shift)
  850.     {
  851.         $temp = new static();
  852.  
  853.         // could just replace lshift with this, but then all lshift() calls would need to be rewritten
  854.         // and I don't want to do that...
  855.         $temp->value = $this->value;
  856.         $temp->rshift($shift);
  857.  
  858.         return $this->normalize($temp);
  859.     }
  860.  
  861.     /**
  862.      * Logical Left Shift
  863.      *
  864.      * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
  865.      *
  866.      * @param int $shift
  867.      * @return PHP
  868.      */
  869.     public function bitwise_leftShift($shift)
  870.     {
  871.         $temp = new static();
  872.         // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
  873.         // and I don't want to do that...
  874.         $temp->value = $this->value;
  875.         $temp->lshift($shift);
  876.  
  877.         return $this->normalize($temp);
  878.     }
  879.  
  880.     /**
  881.      * Converts 32-bit integers to bytes.
  882.      *
  883.      * @param int $x
  884.      * @return string
  885.      */
  886.     private static function int2bytes($x)
  887.     {
  888.         return ltrim(pack('N', $x), chr(0));
  889.     }
  890.  
  891.     /**
  892.      * Array Repeat
  893.      *
  894.      * @param int $input
  895.      * @param int $multiplier
  896.      * @return array
  897.      */
  898.     protected static function array_repeat($input, $multiplier)
  899.     {
  900.         return $multiplier ? array_fill(0, $multiplier, $input) : [];
  901.     }
  902.  
  903.     /**
  904.      * Logical Left Shift
  905.      *
  906.      * Shifts BigInteger's by $shift bits.
  907.      *
  908.      * @param int $shift
  909.      */
  910.     protected function lshift($shift)
  911.     {
  912.         if ($shift == 0) {
  913.             return;
  914.         }
  915.  
  916.         $num_digits = (int)($shift / static::BASE);
  917.         $shift %= static::BASE;
  918.         $shift = 1 << $shift;
  919.  
  920.         $carry = 0;
  921.  
  922.         for ($i = 0; $i < count($this->value); ++$i) {
  923.             $temp = $this->value[$i] * $shift + $carry;
  924.             $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  925.             $this->value[$i] = (int)($temp - $carry * static::BASE_FULL);
  926.         }
  927.  
  928.         if ($carry) {
  929.             $this->value[count($this->value)] = $carry;
  930.         }
  931.  
  932.         while ($num_digits--) {
  933.             array_unshift($this->value, 0);
  934.         }
  935.     }
  936.  
  937.     /**
  938.      * Logical Right Shift
  939.      *
  940.      * Shifts BigInteger's by $shift bits.
  941.      *
  942.      * @param int $shift
  943.      */
  944.     protected function rshift($shift)
  945.     {
  946.         if ($shift == 0) {
  947.             return;
  948.         }
  949.  
  950.         $num_digits = (int)($shift / static::BASE);
  951.         $shift %= static::BASE;
  952.         $carry_shift = static::BASE - $shift;
  953.         $carry_mask = (1 << $shift) - 1;
  954.  
  955.         if ($num_digits) {
  956.             $this->value = array_slice($this->value, $num_digits);
  957.         }
  958.  
  959.         $carry = 0;
  960.  
  961.         for ($i = count($this->value) - 1; $i >= 0; --$i) {
  962.             $temp = $this->value[$i] >> $shift | $carry;
  963.             $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
  964.             $this->value[$i] = $temp;
  965.         }
  966.  
  967.         $this->value = static::trim($this->value);
  968.     }
  969.  
  970.     /**
  971.      * Performs modular exponentiation.
  972.      *
  973.      * @param PHP $e
  974.      * @param PHP $n
  975.      * @return PHP
  976.      */
  977.     protected function powModInner(PHP $e, PHP $n)
  978.     {
  979.         try {
  980.             $class = static::$modexpEngine[static::class];
  981.             return $class::powModHelper($this, $e, $n, static::class);
  982.         } catch (\Exception $err) {
  983.             return PHP\DefaultEngine::powModHelper($this, $e, $n, static::class);
  984.         }
  985.     }
  986.  
  987.     /**
  988.      * Performs squaring
  989.      *
  990.      * @param list<static> $x
  991.      * @return list<static>
  992.      */
  993.     protected static function square(array $x)
  994.     {
  995.         return count($x) < 2 * self::KARATSUBA_CUTOFF ?
  996.             self::trim(self::baseSquare($x)) :
  997.             self::trim(self::karatsubaSquare($x));
  998.     }
  999.  
  1000.     /**
  1001.      * Performs traditional squaring on two BigIntegers
  1002.      *
  1003.      * Squaring can be done faster than multiplying a number by itself can be.  See
  1004.      * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} /
  1005.      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.
  1006.      *
  1007.      * @param array $value
  1008.      * @return array
  1009.      */
  1010.     protected static function baseSquare(array $value)
  1011.     {
  1012.         if (empty($value)) {
  1013.             return [];
  1014.         }
  1015.         $square_value = self::array_repeat(0, 2 * count($value));
  1016.  
  1017.         for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) {
  1018.             $i2 = $i << 1;
  1019.  
  1020.             $temp = $square_value[$i2] + $value[$i] * $value[$i];
  1021.             $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  1022.             $square_value[$i2] = (int)($temp - static::BASE_FULL * $carry);
  1023.  
  1024.             // note how we start from $i+1 instead of 0 as we do in multiplication.
  1025.             for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) {
  1026.                 $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry;
  1027.                 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  1028.                 $square_value[$k] = (int)($temp - static::BASE_FULL * $carry);
  1029.             }
  1030.  
  1031.             // the following line can yield values larger 2**15.  at this point, PHP should switch
  1032.             // over to floats.
  1033.             $square_value[$i + $max_index + 1] = $carry;
  1034.         }
  1035.  
  1036.         return $square_value;
  1037.     }
  1038.  
  1039.     /**
  1040.      * Performs Karatsuba "squaring" on two BigIntegers
  1041.      *
  1042.      * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
  1043.      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.
  1044.      *
  1045.      * @param array $value
  1046.      * @return array
  1047.      */
  1048.     protected static function karatsubaSquare(array $value)
  1049.     {
  1050.         $m = count($value) >> 1;
  1051.  
  1052.         if ($m < self::KARATSUBA_CUTOFF) {
  1053.             return self::baseSquare($value);
  1054.         }
  1055.  
  1056.         $x1 = array_slice($value, $m);
  1057.         $x0 = array_slice($value, 0, $m);
  1058.  
  1059.         $z2 = self::karatsubaSquare($x1);
  1060.         $z0 = self::karatsubaSquare($x0);
  1061.  
  1062.         $z1 = self::addHelper($x1, false, $x0, false);
  1063.         $z1 = self::karatsubaSquare($z1[self::VALUE]);
  1064.         $temp = self::addHelper($z2, false, $z0, false);
  1065.         $z1 = self::subtractHelper($z1, false, $temp[self::VALUE], false);
  1066.  
  1067.         $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
  1068.         $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]);
  1069.  
  1070.         $xx = self::addHelper($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
  1071.         $xx = self::addHelper($xx[self::VALUE], $xx[self::SIGN], $z0, false);
  1072.  
  1073.         return $xx[self::VALUE];
  1074.     }
  1075.  
  1076.     /**
  1077.      * Make the current number odd
  1078.      *
  1079.      * If the current number is odd it'll be unchanged.  If it's even, one will be added to it.
  1080.      *
  1081.      * @see self::randomPrime()
  1082.      */
  1083.     protected function make_odd()
  1084.     {
  1085.         $this->value[0] |= 1;
  1086.     }
  1087.  
  1088.     /**
  1089.      * Test the number against small primes.
  1090.      *
  1091.      * @see self::isPrime()
  1092.      */
  1093.     protected function testSmallPrimes()
  1094.     {
  1095.         if ($this->value == [1]) {
  1096.             return false;
  1097.         }
  1098.         if ($this->value == [2]) {
  1099.             return true;
  1100.         }
  1101.         if (~$this->value[0] & 1) {
  1102.             return false;
  1103.         }
  1104.  
  1105.         $value = $this->value;
  1106.         foreach (static::PRIMES as $prime) {
  1107.             list(, $r) = self::divide_digit($value, $prime);
  1108.             if (!$r) {
  1109.                 return count($value) == 1 && $value[0] == $prime;
  1110.             }
  1111.         }
  1112.  
  1113.         return true;
  1114.     }
  1115.  
  1116.     /**
  1117.      * Scan for 1 and right shift by that amount
  1118.      *
  1119.      * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
  1120.      *
  1121.      * @param PHP $r
  1122.      * @return int
  1123.      * @see self::isPrime()
  1124.      */
  1125.     public static function scan1divide(PHP $r)
  1126.     {
  1127.         $r_value = &$r->value;
  1128.         for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) {
  1129.             $temp = ~$r_value[$i] & static::MAX_DIGIT;
  1130.             for ($j = 1; ($temp >> $j) & 1; ++$j) {
  1131.             }
  1132.             if ($j <= static::BASE) {
  1133.                 break;
  1134.             }
  1135.         }
  1136.         $s = static::BASE * $i + $j;
  1137.         $r->rshift($s);
  1138.         return $s;
  1139.     }
  1140.  
  1141.     /**
  1142.      * Performs exponentiation.
  1143.      *
  1144.      * @param PHP $n
  1145.      * @return PHP
  1146.      */
  1147.     protected function powHelper(PHP $n)
  1148.     {
  1149.         if ($n->compare(static::$zero[static::class]) == 0) {
  1150.             return new static(1);
  1151.         } // n^0 = 1
  1152.  
  1153.         $temp = clone $this;
  1154.         while (!$n->equals(static::$one[static::class])) {
  1155.             $temp = $temp->multiply($this);
  1156.             $n = $n->subtract(static::$one[static::class]);
  1157.         }
  1158.  
  1159.         return $temp;
  1160.     }
  1161.  
  1162.     /**
  1163.      * Is Odd?
  1164.      *
  1165.      * @return bool
  1166.      */
  1167.     public function isOdd()
  1168.     {
  1169.         return (bool)($this->value[0] & 1);
  1170.     }
  1171.  
  1172.     /**
  1173.      * Tests if a bit is set
  1174.      *
  1175.      * @return bool
  1176.      */
  1177.     public function testBit($x)
  1178.     {
  1179.         $digit = (int) floor($x / static::BASE);
  1180.         $bit = $x % static::BASE;
  1181.  
  1182.         if (!isset($this->value[$digit])) {
  1183.             return false;
  1184.         }
  1185.  
  1186.         return (bool)($this->value[$digit] & (1 << $bit));
  1187.     }
  1188.  
  1189.     /**
  1190.      * Is Negative?
  1191.      *
  1192.      * @return bool
  1193.      */
  1194.     public function isNegative()
  1195.     {
  1196.         return $this->is_negative;
  1197.     }
  1198.  
  1199.     /**
  1200.      * Negate
  1201.      *
  1202.      * Given $k, returns -$k
  1203.      *
  1204.      * @return static
  1205.      */
  1206.     public function negate()
  1207.     {
  1208.         $temp = clone $this;
  1209.         $temp->is_negative = !$temp->is_negative;
  1210.  
  1211.         return $temp;
  1212.     }
  1213.  
  1214.     /**
  1215.      * Bitwise Split
  1216.      *
  1217.      * Splits BigInteger's into chunks of $split bits
  1218.      *
  1219.      * @param int $split
  1220.      * @return list<static>
  1221.      */
  1222.     public function bitwise_split($split)
  1223.     {
  1224.         if ($split < 1) {
  1225.             throw new \RuntimeException('Offset must be greater than 1');
  1226.         }
  1227.  
  1228.         $width = (int)($split / static::BASE);
  1229.         if (!$width) {
  1230.             $arr = $this->bitwise_small_split($split);
  1231.             return array_map(function ($digit) {
  1232.                 $temp = new static();
  1233.                 $temp->value = $digit != 0 ? [$digit] : [];
  1234.                 return $temp;
  1235.             }, $arr);
  1236.         }
  1237.  
  1238.         $vals = [];
  1239.         $val = $this->value;
  1240.  
  1241.         $i = $overflow = 0;
  1242.         $len = count($val);
  1243.         while ($i < $len) {
  1244.             $digit = [];
  1245.             if (!$overflow) {
  1246.                 $digit = array_slice($val, $i, $width);
  1247.                 $i += $width;
  1248.                 $overflow = $split % static::BASE;
  1249.                 if ($overflow) {
  1250.                     $mask = (1 << $overflow) - 1;
  1251.                     $temp = isset($val[$i]) ? $val[$i] : 0;
  1252.                     $digit[] = $temp & $mask;
  1253.                 }
  1254.             } else {
  1255.                 $remaining = static::BASE - $overflow;
  1256.                 $tempsplit = $split - $remaining;
  1257.                 $tempwidth = (int)($tempsplit / static::BASE + 1);
  1258.                 $digit = array_slice($val, $i, $tempwidth);
  1259.                 $i += $tempwidth;
  1260.                 $tempoverflow = $tempsplit % static::BASE;
  1261.                 if ($tempoverflow) {
  1262.                     $tempmask = (1 << $tempoverflow) - 1;
  1263.                     $temp = isset($val[$i]) ? $val[$i] : 0;
  1264.                     $digit[] = $temp & $tempmask;
  1265.                 }
  1266.                 $newbits = 0;
  1267.                 for ($j = count($digit) - 1; $j >= 0; $j--) {
  1268.                     $temp = $digit[$j] & $mask;
  1269.                     $digit[$j] = ($digit[$j] >> $overflow) | ($newbits << $remaining);
  1270.                     $newbits = $temp;
  1271.                 }
  1272.                 $overflow = $tempoverflow;
  1273.                 $mask = $tempmask;
  1274.             }
  1275.             $temp = new static();
  1276.             $temp->value = static::trim($digit);
  1277.             $vals[] = $temp;
  1278.         }
  1279.  
  1280.         return array_reverse($vals);
  1281.     }
  1282.  
  1283.     /**
  1284.      * Bitwise Split where $split < static::BASE
  1285.      *
  1286.      * @param int $split
  1287.      * @return list<int>
  1288.      */
  1289.     private function bitwise_small_split($split)
  1290.     {
  1291.         $vals = [];
  1292.         $val = $this->value;
  1293.  
  1294.         $mask = (1 << $split) - 1;
  1295.  
  1296.         $i = $overflow = 0;
  1297.         $len = count($val);
  1298.         $val[] = 0;
  1299.         $remaining = static::BASE;
  1300.         while ($i != $len) {
  1301.             $digit = $val[$i] & $mask;
  1302.             $val[$i] >>= $split;
  1303.             if (!$overflow) {
  1304.                 $remaining -= $split;
  1305.                 $overflow = $split <= $remaining ? 0 : $split - $remaining;
  1306.  
  1307.                 if (!$remaining) {
  1308.                     $i++;
  1309.                     $remaining = static::BASE;
  1310.                     $overflow = 0;
  1311.                 }
  1312.             } elseif (++$i != $len) {
  1313.                 $tempmask = (1 << $overflow) - 1;
  1314.                 $digit |= ($val[$i] & $tempmask) << $remaining;
  1315.                 $val[$i] >>= $overflow;
  1316.                 $remaining = static::BASE - $overflow;
  1317.                 $overflow = $split <= $remaining ? 0 : $split - $remaining;
  1318.             }
  1319.  
  1320.             $vals[] = $digit;
  1321.         }
  1322.  
  1323.         while ($vals[count($vals) - 1] == 0) {
  1324.             unset($vals[count($vals) - 1]);
  1325.         }
  1326.  
  1327.         return array_reverse($vals);
  1328.     }
  1329.  
  1330.     /**
  1331.      * @return bool
  1332.      */
  1333.     protected static function testJITOnWindows()
  1334.     {
  1335.         // see https://github.com/php/php-src/issues/11917
  1336.         if (strtoupper(substr(PHP_OS, 0, 3)) === 'WIN' && function_exists('opcache_get_status') && PHP_VERSION_ID < 80213 && !defined('PHPSECLIB_ALLOW_JIT')) {
  1337.             $status = opcache_get_status();
  1338.             if ($status && isset($status['jit']) && $status['jit']['enabled'] && $status['jit']['on']) {
  1339.                 return true;
  1340.             }
  1341.         }
  1342.         return false;
  1343.     }
  1344. }
  1345.