Source for file Math_BigInteger.php

<?php
/* vim: set expandtab tabstop=4 shiftwidth=4 softtabstop=4: */
 
/**
 * Pure-PHP arbitrary precision integer arithmetic library.
 *
 * Supports base-2, base-10, base-16, and base-256 numbers.  Uses the GMP or BCMath extensions, if available,
 * and an internal implementation, otherwise.
 *
 * PHP versions 4 and 5
 *
 * {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the
 * {@link MATH_BIGINTEGER_MODE_INTERNAL MATH_BIGINTEGER_MODE_INTERNAL} mode)
 *
 * Math_BigInteger uses base-2**26 to perform operations such as multiplication and division and
 * base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction.  Because the largest possible
 * value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating
 * point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are
 * used.  As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %,
 * which only supports integers.  Although this fact will slow this library down, the fact that such a high
 * base is being used should more than compensate.
 *
 * When PHP version 6 is officially released, we'll be able to use 64-bit integers.  This should, once again,
 * allow bitwise operators, and will increase the maximum possible base to 2**31 (or 2**62 for addition /
 * subtraction).
 *
 * Useful resources are as follows:
 *
 *  - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)}
 *  - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)}
 *  - Java's BigInteger classes.  See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip
 *
 * One idea for optimization is to use the comba method to reduce the number of operations performed.
 * MPM uses this quite extensively.  The following URL elaborates:
 *
 * {@link http://www.everything2.com/index.pl?node_id=1736418}}}
 *
 * Here's a quick 'n dirty example of how to use this library:
 * <code>
 * <?php
 *    include('Math_BigInteger.php');
 *
 *    $a = new Math_BigInteger(2);
 *    $b = new Math_BigInteger(3);
 *
 *    $c = $a->add($b);
 *
 *    echo $c->toString(); // outputs 5
 * ?>
 * </code>
 *
 * LICENSE: This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston,
 * MA  02111-1307  USA
 *
 * @category   Math
 * @package    Math_BigInteger
 * @author     Jim Wigginton <terrafrost@php.net>
 * @copyright  MMVI Jim Wigginton
 * @license    http://www.gnu.org/licenses/lgpl.txt
 * @version    CVS: $Id: Math_BigInteger.php,v 1.6 2006/11/16 15:42:08 terrafrost Exp $
 * @link       http://pear.php.net/package/Math_BigInteger
 */
 
/**
 * Include PHP_Compat module bcpowmod since that function does not exist in PHP4:
 * {@link http://pear.php.net/package/PHP_Compat/}
 * {@link http://php.net/function.bcpowmod}
 */
require_once 'PHP/Compat/Function/bcpowmod.php';
// array_fill requires PHP 4.2.0+, per http://php.net/function.array_fill
// see http://www.frostjedi.com/terra/scripts/pear/array_fill.phps
// require_once 'PHP/Compat/Function/array_fill.php';
 
 
 
/**#@+
 * @access private
 * @see Math_BigInteger::_slidingWindow()
 */
/**
 * @see Math_BigInteger::_montgomery()
 * @see Math_BigInteger::_undoMontgomery()
 */
define('MATH_BIGINTEGER_MONTGOMERY', 0);
/**
 * @see Math_BigInteger::_barrett()
 */
define('MATH_BIGINTEGER_BARRETT', 1);
/**
 * @see Math_BigInteger::_mod2()
 */
define('MATH_BIGINTEGER_POWEROF2', 2);
/**
 * @see Math_BigInteger::_remainder()
 */
define('MATH_BIGINTEGER_CLASSIC', 3);
/**
 * @see Math_BigInteger::_copy()
 */
define('MATH_BIGINTEGER_NONE', 4);
/**#@-*/
 
 * @access private
 * @see Math_BigInteger::_montgomery()
 * @see Math_BigInteger::_barrett()
 */
/**
 * $cache[MATH_BIGINTEGER_VARIABLE] tells us whether or not the cached data is still valid.
 */
define('MATH_BIGINTEGER_VARIABLE', 0);
/**
 * $cache[MATH_BIGINTEGER_DATA] contains the cached data.
 */
define('MATH_BIGINTEGER_DATA', 1);
/**#@-*/
 
 * @access private
 * @see Math_BigInteger::Math_BigInteger()
 */
/**
 * To use the pure-PHP implementation
 */
define('MATH_BIGINTEGER_MODE_INTERNAL',1);
/**
 * To use the BCMath library
 *
 * (if enabled; otherwise, the internal implementation will be used)
 */
define('MATH_BIGINTEGER_MODE_BCMATH',2);
/**
 * To use the GMP library
 *
 * (if present; otherwise, either the BCMath or the internal implementation will be used)
 */
define('MATH_BIGINTEGER_MODE_GMP',3);
/**#@-*/
 
 * Pure-PHP arbitrary precission integer arithmetic library. Supports base-2, base-10, base-16, and base-256
 * numbers.  Negative numbers are supported in all publically accessable functions save for modPow
 * and modInverse.
 *
 * @author  Jim Wigginton <terrafrost@php.net>
 * @version 1.0.0RC2
 * @access  public
 * @package Math_BigInteger
 */
class Math_BigInteger {
    /**
     * Holds the BigInteger's value.
     *
     * @var Array 
     * @access private
     */
    var $value;
 
    /**
     * Holds the BigInteger's magnitude.
     *
     * @var Boolean 
     * @access private
     */
    var $is_negative = false;
 
    /**
     * Converts base-2, base-10, base-16, and binary strings (eg. base-256) to BigIntegers.
     *
     * Here's a quick 'n dirty example:
     * <code>
     * <?php
     *    include('Math_BigInteger.php');
     *
     *    $a = new Math_BigInteger('0x32', 16); // 50 in base-16
     *
     *    echo $a->toString(); // outputs 50
     * ?>
     * </code>
     *
     * @param optional $x base-10 number or base-$base number if $base set.
     * @param optional integer $base
     * @return Math_BigInteger 
     * @access public
     */
    function Math_BigInteger($x = 0, $base = 10)
    {
        if ( !defined('MATH_BIGINTEGER_MODE') ) {
            switch (true) {
                case extension_loaded('gmp'):
                    define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_GMP);
                    break;
                case extension_loaded('bcmath'):
                    define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_BCMATH);
                    break;
                default:
                    $this->value = array();
                    define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_INTERNAL);
            }
        }
 
        switch (MATH_BIGINTEGER_MODE) {
            case MATH_BIGINTEGER_MODE_GMP:
                $this->value = gmp_init(0);
                break;
            case MATH_BIGINTEGER_MODE_BCMATH:
                $this->value = '0';
                break;
            default:
                $this->value = array();
        }
 
        if ($x === 0) {
            return;
        }
 
        switch ($base) {
            case 256:
                switch (MATH_BIGINTEGER_MODE) {
                    case MATH_BIGINTEGER_MODE_GMP:
                        $temp = unpack('H*hex', $x);
                        $this->value = gmp_init('0x' . $temp['hex']);
                        break;
                    case MATH_BIGINTEGER_MODE_BCMATH:
                        $len = strlen($x);
                        $len+= (3 * $len) % 4; // rounds $len to the nearest 4.
 
                        $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);
 
                        for ($i = 0; $i < $len; $i+= 4) {
                            $this->value = bcmul($this->value, '4294967296'); // 4294967296 == 2**32
                            $this->value = bcadd($this->value, 0x1000000 * ord($x{$i}) + ((ord($x{$i + 1}) << 16) | (ord($x{$i + 2}) << 8) | ord($x{$i + 3})));
                        }
 
                        break;
                    // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb)
                    case MATH_BIGINTEGER_MODE_INTERNAL:
                        while (strlen($x)) {
                            $this->value[] = $this->_bytes2int($this->_base256_rshift($x, 26));
                        }
                }
                break;
            case 16:
                if ($x{0} == '-') {
                    $this->is_negative = true;
                    $x = substr($x, 1);
                }
 
                $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);
 
                switch (MATH_BIGINTEGER_MODE) {
                    case MATH_BIGINTEGER_MODE_GMP:
                        $temp = $this->is_negative ? '-0x' . $x : '0x' . $x;
                        $this->value = gmp_init($temp);
                        $this->is_negative = false;
                        break;
                    case MATH_BIGINTEGER_MODE_BCMATH:
                        $x = ( strlen($x) & 1 ) ? '0' . $x : $x;
                        $temp = new Math_BigInteger(pack('H*', $x), 256);
                        $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
                        $this->is_negative = false;
                        break;
                    case MATH_BIGINTEGER_MODE_INTERNAL:
                        $x = ( strlen($x) & 1 ) ? '0' . $x : $x;
                        $temp = new Math_BigInteger(pack('H*', $x), 256);
                        $this->value = $temp->value;
                }
                break;
            case 10:
                $x = preg_replace('#^(-?[0-9]*).*#','$1',$x);
 
                switch (MATH_BIGINTEGER_MODE) {
                    case MATH_BIGINTEGER_MODE_GMP:
                        $this->value = gmp_init($x);
                        break;
                    case MATH_BIGINTEGER_MODE_BCMATH:
                        // explicitly casting $x to a string is necessary, here, since doing $x{0} on -1 yields different
                        // results then doing it on '-1' does (modInverse does $x{0})
                        $this->value = (string) $x;
                        break;
                    case MATH_BIGINTEGER_MODE_INTERNAL:
                        $temp = new Math_BigInteger();
 
                        // array(10000000) is 10**7 in base-2**26.  10**7 is the closest to 2**26 we can get without passing it.
                        $multiplier = new Math_BigInteger();
                        $multiplier->value = array(10000000);
 
                        if ($x{0} == '-') {
                            $this->is_negative = true;
                            $x = substr($x, 1);
                        }
 
                        $x = str_pad($x, strlen($x) + (6 * strlen($x)) % 7, 0, STR_PAD_LEFT);
 
                        while (strlen($x)) {
                            $temp = $temp->multiply($multiplier);
                            $temp = $temp->add(new Math_BigInteger($this->_int2bytes(substr($x, 0, 7)), 256));
                            $x = substr($x, 7);
                        }
 
                        $this->value = $temp->value;
                }
                break;
            case 2: // base-2 support originally implemented by Lluis Pamies - thanks!
                if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP) {
                    $this->value = gmp_init($x, 2);
                    break;
                }
 
                if ($x{0} == '-') {
                    $this->is_negative = true;
                    $x = substr($x, 1);
                }
 
                $x = preg_replace('#^([01]*).*#', '$1', $x);
                $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT);
 
                $str = '0x';
                while (strlen($x)) {
                   $part = substr($x, 0, 4);
                   $str.= dechex(bindec($part));
                   $x = substr($x, 4);
                }
 
                $temp = new Math_BigInteger($str, 16);
                $this->value = $temp->value;
 
                if (MATH_BINGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH && $this->is_negative) {
                    $this->value = '-' . $this->value;
                    $this->is_negative = false;
                }
 
                break;
            default:
                // base not supported, so we'll let $this == 0
        }
    }
 
    /**
     * Converts a BigInteger to a byte string (eg. base-256).
     *
     * Here's a quick 'n dirty example:
     * <code>
     * <?php
     *    include('Math_BigInteger.php');
     *
     *    $a = new Math_BigInteger('65');
     *
     *    echo $a->toBytes(); // outputs chr(65)
     * ?>
     * </code>
     *
     * @return String 
     * @access public
     * @internal Converts a base-2**26 number to base-2**8
     */
    function toBytes()
    {
        switch ( MATH_BIGINTEGER_MODE ) {
            case MATH_BIGINTEGER_MODE_GMP:
                if (gmp_cmp($this->value, gmp_init(0)) == 0) {
                    return '';
                }
 
                $temp = gmp_strval(gmp_abs($this->value), 16);
                $temp = ( strlen($temp) & 1 ) ? '0' . $temp : $temp;
 
                return ltrim(pack('H*', $temp), chr(0));
            case MATH_BIGINTEGER_MODE_BCMATH:
                if ($this->value === '0') {
                    return '';
                }
 
                $value = '';
                $current = $this->value;                 
 
                // we don't do four bytes at a time because then numbers larger than 1<<31 would be negative
                // two's complimented numbers, which would break chr.
                while (bccomp($current, '0') > 0) {
                    $temp = bcmod($current, 0x1000000);
                    $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
                    $current = bcdiv($current, 0x1000000);
                }
 
                return ltrim($value, chr(0));
        }
 
        if (!count($this->value)) {
            return '';
        }
 
        $result = $this->_int2bytes($this->value[count($this->value) - 1]);
 
        $temp = $this->_copy();
 
        for ($i = count($temp->value) - 2; $i >= 0; $i--) {
            $temp->_base256_lshift($result, 26);
            $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
        }
 
        return $result;
    }
 
    /**
     * Converts a BigInteger to a base-10 number.
     *
     * Here's a quick 'n dirty example:
     * <code>
     * <?php
     *    include('Math_BigInteger.php');
     *
     *    $a = new Math_BigInteger('50');
     *
     *    echo $a->toString(); // outputs 50
     * ?>
     * </code>
     *
     * @return String 
     * @access public
     * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10)
     */
    function toString()
    {
        switch ( MATH_BIGINTEGER_MODE ) {
            case MATH_BIGINTEGER_MODE_GMP:
                return gmp_strval($this->value);
            case MATH_BIGINTEGER_MODE_BCMATH:
                if ($this->value === '0') {
                    return '0';
                }
 
                return ltrim($this->value, '0');
        }
 
        if (!count($this->value)) {
            return '0';
        }
 
        $result = ($this->is_negative) ? '-' : '';
 
        $temp = $this->_copy();
 
        $divisor = new Math_BigInteger();
        $divisor->value = array(10000000); // eg. 10**7
 
        while (count($temp->value)) {
            list($temp, $mod) = $temp->divide($divisor);
            $result = str_pad($this->_bytes2int($mod->toBytes()), 7, '0', STR_PAD_LEFT) . $result;
        }
 
        return ltrim($result, '0');
    }
 
    /**
     * Adds two BigIntegers.
     *
     * Here's a quick 'n dirty example:
     * <code>
     * <?php
     *    include('Math_BigInteger.php');
     *
     *    $a = new Math_BigInteger('10');
     *    $b = new Math_BigInteger('20');
     *
     *    $c = $a->add($b);
     *
     *    echo $c->toString(); // outputs 30
     * ?>
     * </code>
     *
     * @param Math_BigInteger $y 
     * @return Math_BigInteger 
     * @access public
     * @internal Performs base-2**52 addition
     */
    function add($y)
    {
        switch ( MATH_BIGINTEGER_MODE ) {
            case MATH_BIGINTEGER_MODE_GMP:
                $temp = new Math_BigInteger();
                $temp->value = gmp_add($this->value, $y->value);
 
                return $temp;
            case MATH_BIGINTEGER_MODE_BCMATH:
                $temp = new Math_BigInteger();
                $temp->value = bcadd($this->value, $y->value);
 
                return $temp;
        }
 
        // subtract, if appropriate
        if ( $this->is_negative != $y->is_negative ) {
            // is $y the negative number?
            $y_negative = $this->compare($y) > 0;
 
            $temp = $this->_copy();
            $y = $y->_copy();
            $temp->is_negative = $y->is_negative = false;
 
            $diff = $temp->compare($y);
            if ( !$diff ) {
                return new Math_BigInteger();
            }
 
            $temp = $temp->subtract($y);
 
            $temp->is_negative = ($diff > 0) ? !$y_negative : $y_negative;
 
            return $temp;
        }
 
        $result = new Math_BigInteger();
        $carry = 0;
 
        $size = max(count($this->value), count($y->value));
        $size+= $size % 2; // rounds $size to the nearest 2.
 
        $x = array_pad($this->value, $size,0);
        $y = array_pad($y->value, $size, 0);
 
        for ($i = 0; $i < $size - 1; $i+=2) {
            $sum = $x[$i + 1] * 0x4000000 + $x[$i] + $y[$i + 1] * 0x4000000 + $y[$i] + $carry;
            $carry = $sum >= 4503599627370496; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
            $sum = $carry ? $sum - 4503599627370496 : $sum;
 
            $temp = floor($sum / 0x4000000);
 
            $result->value[] = $sum - 0x4000000 * $temp; // eg. a faster alternative to fmod($sum,0x4000000)
            $result->value[] = $temp;
        }
 
        if ($carry) {
            $result->value[] = $carry;
        }
 
        $result->is_negative = $this->is_negative;
 
        return $result->_normalize();
    }
 
    /**
     * Subtracts two BigIntegers.
     *
     * Here's a quick 'n dirty example:
     * <code>
     * <?php
     *    include('Math_BigInteger.php');
     *
     *    $a = new Math_BigInteger('10');
     *    $b = new Math_BigInteger('20');
     *
     *    $c = $a->subtract($b);
     *
     *    echo $c->toString(); // outputs -10
     * ?>
     * </code>
     *
     * @param Math_BigInteger $y 
     * @return Math_BigInteger 
     * @access public
     * @internal Performs base-2**52 subtraction
     */
    function subtract($y)
    {
        switch ( MATH_BIGINTEGER_MODE ) {
            case MATH_BIGINTEGER_MODE_GMP:
                $temp = new Math_BigInteger();
                $temp->value = gmp_sub($this->value, $y->value);
 
                return $temp;
            case MATH_BIGINTEGER_MODE_BCMATH:
                $temp = new Math_BigInteger();
                $temp->value = bcsub($this->value, $y->value);
 
                return $temp;
        }
 
        // add, if appropriate
        if ( $this->is_negative != $y->is_negative ) {
            $is_negative = $y->compare($this) > 0;
 
            $temp = $this->_copy();
            $y = $y->_copy();
            $temp->is_negative = $y->is_negative = false;
 
            $temp = $temp->add($y);
 
            $temp->is_negative = $is_negative;
 
            return $temp;
        }
 
        $diff = $this->compare($y);
 
        if ( !$diff ) {
            return new Math_BigInteger();
        }
 
        // switch $this and $y around, if appropriate.
        if ( (!$this->is_negative && $diff < 0) || ($this->is_negative && $diff > 0) ) {
            $is_negative = $y->is_negative;
 
            $temp = $this->_copy();
            $y = $y->_copy();
            $temp->is_negative = $y->is_negative = false;
 
            $temp = $y->subtract($temp);
            $temp->is_negative = !$is_negative;
 
            return $temp;
        }
 
        $result = new Math_BigInteger();
        $carry = 0;
 
        $size = max(count($this->value), count($y->value));
        $size+= $size % 2;
 
        $x = array_pad($this->value, $size, 0);
        $y = array_pad($y->value, $size, 0);
 
        for ($i = 0; $i < $size - 1;$i+=2) {