Subversion Repositories oidplus

Rev

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