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 32-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 32-bit Engine.
  20.  *
  21.  * Uses 64-bit floats if int size is 4 bits
  22.  *
  23.  * @package PHP32
  24.  * @author  Jim Wigginton <terrafrost@php.net>
  25.  * @access  public
  26.  */
  27. class PHP32 extends PHP
  28. {
  29.     // Constants used by PHP.php
  30.     const BASE = 26;
  31.     const BASE_FULL = 0x4000000;
  32.     const MAX_DIGIT = 0x3FFFFFF;
  33.     const MSB = 0x2000000;
  34.  
  35.     /**
  36.      * MAX10 in greatest MAX10LEN satisfying
  37.      * MAX10 = 10**MAX10LEN <= 2**BASE.
  38.      */
  39.     const MAX10 = 10000000;
  40.  
  41.     /**
  42.      * MAX10LEN in greatest MAX10LEN satisfying
  43.      * MAX10 = 10**MAX10LEN <= 2**BASE.
  44.      */
  45.     const MAX10LEN = 7;
  46.     const MAX_DIGIT2 = 4503599627370496;
  47.  
  48.     /**
  49.      * Initialize a PHP32 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) & 3;
  83.             if ($step) {
  84.                 $digit >>= 2 * $step;
  85.             }
  86.             if ($step != 3) {
  87.                 $digit &= static::MAX_DIGIT;
  88.                 $i++;
  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 >= 4;
  107.     }
  108.  
  109.     /**
  110.      * Adds two BigIntegers.
  111.      *
  112.      * @param PHP32 $y
  113.      * @return PHP32
  114.      */
  115.     public function add(PHP32 $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 PHP32 $y
  126.      * @return PHP32
  127.      */
  128.     public function subtract(PHP32 $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 PHP32 $y
  139.      * @return PHP32
  140.      */
  141.     public function multiply(PHP32 $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 PHP32 $y
  157.      * @return array{PHP32, PHP32}
  158.      */
  159.     public function divide(PHP32 $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 PHP32 $n
  169.      * @return false|PHP32
  170.      */
  171.     public function modInverse(PHP32 $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 PHP32 $n
  181.      * @return PHP32[]
  182.      */
  183.     public function extendedGCD(PHP32 $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 PHP32 $n
  194.      * @return PHP32
  195.      */
  196.     public function gcd(PHP32 $n)
  197.     {
  198.         return $this->extendedGCD($n)['gcd'];
  199.     }
  200.  
  201.     /**
  202.      * Logical And
  203.      *
  204.      * @param PHP32 $x
  205.      * @return PHP32
  206.      */
  207.     public function bitwise_and(PHP32 $x)
  208.     {
  209.         return $this->bitwiseAndHelper($x);
  210.     }
  211.  
  212.     /**
  213.      * Logical Or
  214.      *
  215.      * @param PHP32 $x
  216.      * @return PHP32
  217.      */
  218.     public function bitwise_or(PHP32 $x)
  219.     {
  220.         return $this->bitwiseOrHelper($x);
  221.     }
  222.  
  223.     /**
  224.      * Logical Exclusive Or
  225.      *
  226.      * @param PHP32 $x
  227.      * @return PHP32
  228.      */
  229.     public function bitwise_xor(PHP32 $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 PHP32 $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.      * @access public
  251.      * @see self::equals()
  252.      */
  253.     public function compare(PHP32 $y)
  254.     {
  255.         return $this->compareHelper($this->value, $this->is_negative, $y->value, $y->is_negative);
  256.     }
  257.  
  258.     /**
  259.      * Tests the equality of two numbers.
  260.      *
  261.      * If you need to see if one number is greater than or less than another number, use BigInteger::compare()
  262.      *
  263.      * @param PHP32 $x
  264.      * @return bool
  265.      */
  266.     public function equals(PHP32 $x)
  267.     {
  268.         return $this->value === $x->value && $this->is_negative == $x->is_negative;
  269.     }
  270.  
  271.     /**
  272.      * Performs modular exponentiation.
  273.      *
  274.      * @param PHP32 $e
  275.      * @param PHP32 $n
  276.      * @return PHP32
  277.      */
  278.     public function modPow(PHP32 $e, PHP32 $n)
  279.     {
  280.         return $this->powModOuter($e, $n);
  281.     }
  282.  
  283.     /**
  284.      * Performs modular exponentiation.
  285.      *
  286.      * Alias for modPow().
  287.      *
  288.      * @param PHP32 $e
  289.      * @param PHP32 $n
  290.      * @return PHP32
  291.      */
  292.     public function powMod(PHP32 $e, PHP32 $n)
  293.     {
  294.         return $this->powModOuter($e, $n);
  295.     }
  296.  
  297.     /**
  298.      * Generate a random prime number between a range
  299.      *
  300.      * If there's not a prime within the given range, false will be returned.
  301.      *
  302.      * @param PHP32 $min
  303.      * @param PHP32 $max
  304.      * @return false|PHP32
  305.      */
  306.     public static function randomRangePrime(PHP32 $min, PHP32 $max)
  307.     {
  308.         return self::randomRangePrimeOuter($min, $max);
  309.     }
  310.  
  311.     /**
  312.      * Generate a random number between a range
  313.      *
  314.      * Returns a random number between $min and $max where $min and $max
  315.      * can be defined using one of the two methods:
  316.      *
  317.      * BigInteger::randomRange($min, $max)
  318.      * BigInteger::randomRange($max, $min)
  319.      *
  320.      * @param PHP32 $min
  321.      * @param PHP32 $max
  322.      * @return PHP32
  323.      */
  324.     public static function randomRange(PHP32 $min, PHP32 $max)
  325.     {
  326.         return self::randomRangeHelper($min, $max);
  327.     }
  328.  
  329.     /**
  330.      * Performs exponentiation.
  331.      *
  332.      * @param PHP32 $n
  333.      * @return PHP32
  334.      */
  335.     public function pow(PHP32 $n)
  336.     {
  337.         return $this->powHelper($n);
  338.     }
  339.  
  340.     /**
  341.      * Return the minimum BigInteger between an arbitrary number of BigIntegers.
  342.      *
  343.      * @param PHP32 ...$nums
  344.      * @return PHP32
  345.      */
  346.     public static function min(PHP32 ...$nums)
  347.     {
  348.         return self::minHelper($nums);
  349.     }
  350.  
  351.     /**
  352.      * Return the maximum BigInteger between an arbitrary number of BigIntegers.
  353.      *
  354.      * @param PHP32 ...$nums
  355.      * @return PHP32
  356.      */
  357.     public static function max(PHP32 ...$nums)
  358.     {
  359.         return self::maxHelper($nums);
  360.     }
  361.  
  362.     /**
  363.      * Tests BigInteger to see if it is between two integers, inclusive
  364.      *
  365.      * @param PHP32 $min
  366.      * @param PHP32 $max
  367.      * @return bool
  368.      */
  369.     public function between(PHP32 $min, PHP32 $max)
  370.     {
  371.         return $this->compare($min) >= 0 && $this->compare($max) <= 0;
  372.     }
  373. }
  374.