Subversion Repositories oidplus

Rev

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