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 64-bit 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. /**
  19.  * Pure-PHP 64-bit Engine.
  20.  *
  21.  * Uses 64-bit integers if int size is 8 bits
  22.  *
  23.  * @package PHP
  24.  * @author  Jim Wigginton <terrafrost@php.net>
  25.  * @access  public
  26.  */
  27. class PHP64 extends PHP
  28. {
  29.     // Constants used by PHP.php
  30.     const BASE = 31;
  31.     const BASE_FULL = 0x80000000;
  32.     const MAX_DIGIT = 0x7FFFFFFF;
  33.     const MSB = 0x40000000;
  34.  
  35.     /**
  36.      * MAX10 in greatest MAX10LEN satisfying
  37.      * MAX10 = 10**MAX10LEN <= 2**BASE.
  38.      */
  39.     const MAX10 = 1000000000;
  40.  
  41.     /**
  42.      * MAX10LEN in greatest MAX10LEN satisfying
  43.      * MAX10 = 10**MAX10LEN <= 2**BASE.
  44.      */
  45.     const MAX10LEN = 9;
  46.     const MAX_DIGIT2 = 4611686018427387904;
  47.  
  48.     /**
  49.      * Initialize a PHP64 BigInteger Engine instance
  50.      *
  51.      * @param int $base
  52.      * @see parent::initialize()
  53.      */
  54.     protected function initialize($base)
  55.     {
  56.         if ($base != 256 && $base != -256) {
  57.             return parent::initialize($base);
  58.         }
  59.  
  60.         $val = $this->value;
  61.         $this->value = [];
  62.         $vals = &$this->value;
  63.         $i = strlen($val);
  64.         if (!$i) {
  65.             return;
  66.         }
  67.  
  68.         while (true) {
  69.             $i -= 4;
  70.             if ($i < 0) {
  71.                 if ($i == -4) {
  72.                     break;
  73.                 }
  74.                 $val = substr($val, 0, 4 + $i);
  75.                 $val = str_pad($val, 4, "\0", STR_PAD_LEFT);
  76.                 if ($val == "\0\0\0\0") {
  77.                     break;
  78.                 }
  79.                 $i = 0;
  80.             }
  81.             list(, $digit) = unpack('N', substr($val, $i, 4));
  82.             $step = count($vals) & 7;
  83.             if (!$step) {
  84.                 $digit &= static::MAX_DIGIT;
  85.                 $i++;
  86.             } else {
  87.                 $shift = 8 - $step;
  88.                 $digit >>= $shift;
  89.                 $shift = 32 - $shift;
  90.                 $digit &= (1 << $shift) - 1;
  91.                 $temp = $i > 0 ? ord($val[$i - 1]) : 0;
  92.                 $digit |= ($temp << $shift) & 0x7F000000;
  93.             }
  94.             $vals[] = $digit;
  95.         }
  96.         while (end($vals) === 0) {
  97.             array_pop($vals);
  98.         }
  99.         reset($vals);
  100.     }
  101.  
  102.     /**
  103.      * Test for engine validity
  104.      *
  105.      * @see parent::__construct()
  106.      * @return bool
  107.      */
  108.     public static function isValidEngine()
  109.     {
  110.         return PHP_INT_SIZE >= 8;
  111.     }
  112.  
  113.     /**
  114.      * Adds two BigIntegers.
  115.      *
  116.      * @param PHP64 $y
  117.      * @return PHP64
  118.      */
  119.     public function add(PHP64 $y)
  120.     {
  121.         $temp = self::addHelper($this->value, $this->is_negative, $y->value, $y->is_negative);
  122.  
  123.         return $this->convertToObj($temp);
  124.     }
  125.  
  126.     /**
  127.      * Subtracts two BigIntegers.
  128.      *
  129.      * @param PHP64 $y
  130.      * @return PHP64
  131.      */
  132.     public function subtract(PHP64 $y)
  133.     {
  134.         $temp = self::subtractHelper($this->value, $this->is_negative, $y->value, $y->is_negative);
  135.  
  136.         return $this->convertToObj($temp);
  137.     }
  138.  
  139.     /**
  140.      * Multiplies two BigIntegers.
  141.      *
  142.      * @param PHP64 $y
  143.      * @return PHP64
  144.      */
  145.     public function multiply(PHP64 $y)
  146.     {
  147.         $temp = self::multiplyHelper($this->value, $this->is_negative, $y->value, $y->is_negative);
  148.  
  149.         return $this->convertToObj($temp);
  150.     }
  151.  
  152.     /**
  153.      * Divides two BigIntegers.
  154.      *
  155.      * Returns an array whose first element contains the quotient and whose second element contains the
  156.      * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
  157.      * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
  158.      * and the divisor (basically, the "common residue" is the first positive modulo).
  159.      *
  160.      * @param PHP64 $y
  161.      * @return array{PHP64, PHP64}
  162.      */
  163.     public function divide(PHP64 $y)
  164.     {
  165.         return $this->divideHelper($y);
  166.     }
  167.  
  168.     /**
  169.      * Calculates modular inverses.
  170.      *
  171.      * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
  172.      * @param PHP64 $n
  173.      * @return false|PHP64
  174.      */
  175.     public function modInverse(PHP64 $n)
  176.     {
  177.         return $this->modInverseHelper($n);
  178.     }
  179.  
  180.     /**
  181.      * Calculates modular inverses.
  182.      *
  183.      * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
  184.      * @param PHP64 $n
  185.      * @return PHP64[]
  186.      */
  187.     public function extendedGCD(PHP64 $n)
  188.     {
  189.         return $this->extendedGCDHelper($n);
  190.     }
  191.  
  192.     /**
  193.      * Calculates the greatest common divisor
  194.      *
  195.      * Say you have 693 and 609.  The GCD is 21.
  196.      *
  197.      * @param PHP64 $n
  198.      * @return PHP64
  199.      */
  200.     public function gcd(PHP64 $n)
  201.     {
  202.         return $this->extendedGCD($n)['gcd'];
  203.     }
  204.  
  205.     /**
  206.      * Logical And
  207.      *
  208.      * @param PHP64 $x
  209.      * @return PHP64
  210.      */
  211.     public function bitwise_and(PHP64 $x)
  212.     {
  213.         return $this->bitwiseAndHelper($x);
  214.     }
  215.  
  216.     /**
  217.      * Logical Or
  218.      *
  219.      * @param PHP64 $x
  220.      * @return PHP64
  221.      */
  222.     public function bitwise_or(PHP64 $x)
  223.     {
  224.         return $this->bitwiseOrHelper($x);
  225.     }
  226.  
  227.     /**
  228.      * Logical Exclusive Or
  229.      *
  230.      * @param PHP64 $x
  231.      * @return PHP64
  232.      */
  233.     public function bitwise_xor(PHP64 $x)
  234.     {
  235.         return $this->bitwiseXorHelper($x);
  236.     }
  237.  
  238.     /**
  239.      * Compares two numbers.
  240.      *
  241.      * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite.  The reason for this is
  242.      * demonstrated thusly:
  243.      *
  244.      * $x  > $y: $x->compare($y)  > 0
  245.      * $x  < $y: $x->compare($y)  < 0
  246.      * $x == $y: $x->compare($y) == 0
  247.      *
  248.      * Note how the same comparison operator is used.  If you want to test for equality, use $x->equals($y).
  249.      *
  250.      * {@internal Could return $this->subtract($x), but that's not as fast as what we do do.}
  251.      *
  252.      * @param PHP64 $y
  253.      * @return int in case < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
  254.      * @access public
  255.      * @see self::equals()
  256.      */
  257.     public function compare(PHP64 $y)
  258.     {
  259.         return parent::compareHelper($this->value, $this->is_negative, $y->value, $y->is_negative);
  260.     }
  261.  
  262.     /**
  263.      * Tests the equality of two numbers.
  264.      *
  265.      * If you need to see if one number is greater than or less than another number, use BigInteger::compare()
  266.      *
  267.      * @param PHP64 $x
  268.      * @return bool
  269.      */
  270.     public function equals(PHP64 $x)
  271.     {
  272.         return $this->value === $x->value && $this->is_negative == $x->is_negative;
  273.     }
  274.  
  275.     /**
  276.      * Performs modular exponentiation.
  277.      *
  278.      * @param PHP64 $e
  279.      * @param PHP64 $n
  280.      * @return PHP64
  281.      */
  282.     public function modPow(PHP64 $e, PHP64 $n)
  283.     {
  284.         return $this->powModOuter($e, $n);
  285.     }
  286.  
  287.     /**
  288.      * Performs modular exponentiation.
  289.      *
  290.      * Alias for modPow().
  291.      *
  292.      * @param PHP64 $e
  293.      * @param PHP64 $n
  294.      * @return PHP64|false
  295.      */
  296.     public function powMod(PHP64 $e, PHP64 $n)
  297.     {
  298.         return $this->powModOuter($e, $n);
  299.     }
  300.  
  301.     /**
  302.      * Generate a random prime number between a range
  303.      *
  304.      * If there's not a prime within the given range, false will be returned.
  305.      *
  306.      * @param PHP64 $min
  307.      * @param PHP64 $max
  308.      * @return false|PHP64
  309.      */
  310.     public static function randomRangePrime(PHP64 $min, PHP64 $max)
  311.     {
  312.         return self::randomRangePrimeOuter($min, $max);
  313.     }
  314.  
  315.     /**
  316.      * Generate a random number between a range
  317.      *
  318.      * Returns a random number between $min and $max where $min and $max
  319.      * can be defined using one of the two methods:
  320.      *
  321.      * BigInteger::randomRange($min, $max)
  322.      * BigInteger::randomRange($max, $min)
  323.      *
  324.      * @param PHP64 $min
  325.      * @param PHP64 $max
  326.      * @return PHP64
  327.      */
  328.     public static function randomRange(PHP64 $min, PHP64 $max)
  329.     {
  330.         return self::randomRangeHelper($min, $max);
  331.     }
  332.  
  333.     /**
  334.      * Performs exponentiation.
  335.      *
  336.      * @param PHP64 $n
  337.      * @return PHP64
  338.      */
  339.     public function pow(PHP64 $n)
  340.     {
  341.         return $this->powHelper($n);
  342.     }
  343.  
  344.     /**
  345.      * Return the minimum BigInteger between an arbitrary number of BigIntegers.
  346.      *
  347.      * @param PHP64 ...$nums
  348.      * @return PHP64
  349.      */
  350.     public static function min(PHP64 ...$nums)
  351.     {
  352.         return self::minHelper($nums);
  353.     }
  354.  
  355.     /**
  356.      * Return the maximum BigInteger between an arbitrary number of BigIntegers.
  357.      *
  358.      * @param PHP64 ...$nums
  359.      * @return PHP64
  360.      */
  361.     public static function max(PHP64 ...$nums)
  362.     {
  363.         return self::maxHelper($nums);
  364.     }
  365.  
  366.     /**
  367.      * Tests BigInteger to see if it is between two integers, inclusive
  368.      *
  369.      * @param PHP64 $min
  370.      * @param PHP64 $max
  371.      * @return bool
  372.      */
  373.     public function between(PHP64 $min, PHP64 $max)
  374.     {
  375.         return $this->compare($min) >= 0 && $this->compare($max) <= 0;
  376.     }
  377. }
  378.