Subversion Repositories oidplus

Rev

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