[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * BigMath: A math library wrapper that abstracts out the underlying
   5   * long integer library.
   6   *
   7   * PHP versions 4 and 5
   8   *
   9   * LICENSE: See the COPYING file included in this distribution.
  10   *
  11   * @access private
  12   * @package OpenID
  13   * @author JanRain, Inc. <openid@janrain.com>
  14   * @copyright 2005-2008 Janrain, Inc.
  15   * @license http://www.apache.org/licenses/LICENSE-2.0 Apache
  16   */
  17  
  18  // Do not allow direct access
  19  defined( '_JEXEC' ) or die( 'Restricted access' );
  20  
  21  /**
  22   * Needed for random number generation
  23   */
  24  require_once 'Auth/OpenID/CryptUtil.php';
  25  
  26  /**
  27   * Need Auth_OpenID::bytes().
  28   */
  29  require_once 'Auth/OpenID.php';
  30  
  31  /**
  32   * The superclass of all big-integer math implementations
  33   * @access private
  34   * @package OpenID
  35   */
  36  class Auth_OpenID_MathLibrary {
  37      /**
  38       * Given a long integer, returns the number converted to a binary
  39       * string.  This function accepts long integer values of arbitrary
  40       * magnitude and uses the local large-number math library when
  41       * available.
  42       *
  43       * @param integer $long The long number (can be a normal PHP
  44       * integer or a number created by one of the available long number
  45       * libraries)
  46       * @return string $binary The binary version of $long
  47       */
  48      function longToBinary($long)
  49      {
  50          $cmp = $this->cmp($long, 0);
  51          if ($cmp < 0) {
  52              $msg = __FUNCTION__ . " takes only positive integers.";
  53              trigger_error($msg, E_USER_ERROR);
  54              return null;
  55          }
  56  
  57          if ($cmp == 0) {
  58              return "\x00";
  59          }
  60  
  61          $bytes = array();
  62  
  63          while ($this->cmp($long, 0) > 0) {
  64              array_unshift($bytes, $this->mod($long, 256));
  65              $long = $this->div($long, pow(2, 8));
  66          }
  67  
  68          if ($bytes && ($bytes[0] > 127)) {
  69              array_unshift($bytes, 0);
  70          }
  71  
  72          $string = '';
  73          foreach ($bytes as $byte) {
  74              $string .= pack('C', $byte);
  75          }
  76  
  77          return $string;
  78      }
  79  
  80      /**
  81       * Given a binary string, returns the binary string converted to a
  82       * long number.
  83       *
  84       * @param string $binary The binary version of a long number,
  85       * probably as a result of calling longToBinary
  86       * @return integer $long The long number equivalent of the binary
  87       * string $str
  88       */
  89      function binaryToLong($str)
  90      {
  91          if ($str === null) {
  92              return null;
  93          }
  94  
  95          // Use array_merge to return a zero-indexed array instead of a
  96          // one-indexed array.
  97          $bytes = array_merge(unpack('C*', $str));
  98  
  99          $n = $this->init(0);
 100  
 101          if ($bytes && ($bytes[0] > 127)) {
 102              trigger_error("bytesToNum works only for positive integers.",
 103                            E_USER_WARNING);
 104              return null;
 105          }
 106  
 107          foreach ($bytes as $byte) {
 108              $n = $this->mul($n, pow(2, 8));
 109              $n = $this->add($n, $byte);
 110          }
 111  
 112          return $n;
 113      }
 114  
 115      function base64ToLong($str)
 116      {
 117          $b64 = base64_decode($str);
 118  
 119          if ($b64 === false) {
 120              return false;
 121          }
 122  
 123          return $this->binaryToLong($b64);
 124      }
 125  
 126      function longToBase64($str)
 127      {
 128          return base64_encode($this->longToBinary($str));
 129      }
 130  
 131      /**
 132       * Returns a random number in the specified range.  This function
 133       * accepts $start, $stop, and $step values of arbitrary magnitude
 134       * and will utilize the local large-number math library when
 135       * available.
 136       *
 137       * @param integer $start The start of the range, or the minimum
 138       * random number to return
 139       * @param integer $stop The end of the range, or the maximum
 140       * random number to return
 141       * @param integer $step The step size, such that $result - ($step
 142       * * N) = $start for some N
 143       * @return integer $result The resulting randomly-generated number
 144       */
 145      function rand($stop)
 146      {
 147          static $duplicate_cache = array();
 148  
 149          // Used as the key for the duplicate cache
 150          $rbytes = $this->longToBinary($stop);
 151  
 152          if (array_key_exists($rbytes, $duplicate_cache)) {
 153              list($duplicate, $nbytes) = $duplicate_cache[$rbytes];
 154          } else {
 155              if ($rbytes[0] == "\x00") {
 156                  $nbytes = Auth_OpenID::bytes($rbytes) - 1;
 157              } else {
 158                  $nbytes = Auth_OpenID::bytes($rbytes);
 159              }
 160  
 161              $mxrand = $this->pow(256, $nbytes);
 162  
 163              // If we get a number less than this, then it is in the
 164              // duplicated range.
 165              $duplicate = $this->mod($mxrand, $stop);
 166  
 167              if (count($duplicate_cache) > 10) {
 168                  $duplicate_cache = array();
 169              }
 170  
 171              $duplicate_cache[$rbytes] = array($duplicate, $nbytes);
 172          }
 173  
 174          do {
 175              $bytes = "\x00" . Auth_OpenID_CryptUtil::getBytes($nbytes);
 176              $n = $this->binaryToLong($bytes);
 177              // Keep looping if this value is in the low duplicated range
 178          } while ($this->cmp($n, $duplicate) < 0);
 179  
 180          return $this->mod($n, $stop);
 181      }
 182  }
 183  
 184  /**
 185   * Exposes BCmath math library functionality.
 186   *
 187   * {@link Auth_OpenID_BcMathWrapper} wraps the functionality provided
 188   * by the BCMath extension.
 189   *
 190   * @access private
 191   * @package OpenID
 192   */
 193  class Auth_OpenID_BcMathWrapper extends Auth_OpenID_MathLibrary{
 194      var $type = 'bcmath';
 195  
 196      function add($x, $y)
 197      {
 198          return bcadd($x, $y);
 199      }
 200  
 201      function sub($x, $y)
 202      {
 203          return bcsub($x, $y);
 204      }
 205  
 206      function pow($base, $exponent)
 207      {
 208          return bcpow($base, $exponent);
 209      }
 210  
 211      function cmp($x, $y)
 212      {
 213          return bccomp($x, $y);
 214      }
 215  
 216      function init($number, $base = 10)
 217      {
 218          return $number;
 219      }
 220  
 221      function mod($base, $modulus)
 222      {
 223          return bcmod($base, $modulus);
 224      }
 225  
 226      function mul($x, $y)
 227      {
 228          return bcmul($x, $y);
 229      }
 230  
 231      function div($x, $y)
 232      {
 233          return bcdiv($x, $y);
 234      }
 235  
 236      /**
 237       * Same as bcpowmod when bcpowmod is missing
 238       *
 239       * @access private
 240       */
 241      function _powmod($base, $exponent, $modulus)
 242      {
 243          $square = $this->mod($base, $modulus);
 244          $result = 1;
 245          while($this->cmp($exponent, 0) > 0) {
 246              if ($this->mod($exponent, 2)) {
 247                  $result = $this->mod($this->mul($result, $square), $modulus);
 248              }
 249              $square = $this->mod($this->mul($square, $square), $modulus);
 250              $exponent = $this->div($exponent, 2);
 251          }
 252          return $result;
 253      }
 254  
 255      function powmod($base, $exponent, $modulus)
 256      {
 257          if (function_exists('bcpowmod')) {
 258              return bcpowmod($base, $exponent, $modulus);
 259          } else {
 260              return $this->_powmod($base, $exponent, $modulus);
 261          }
 262      }
 263  
 264      function toString($num)
 265      {
 266          return $num;
 267      }
 268  }
 269  
 270  /**
 271   * Exposes GMP math library functionality.
 272   *
 273   * {@link Auth_OpenID_GmpMathWrapper} wraps the functionality provided
 274   * by the GMP extension.
 275   *
 276   * @access private
 277   * @package OpenID
 278   */
 279  class Auth_OpenID_GmpMathWrapper extends Auth_OpenID_MathLibrary{
 280      var $type = 'gmp';
 281  
 282      function add($x, $y)
 283      {
 284          return gmp_add($x, $y);
 285      }
 286  
 287      function sub($x, $y)
 288      {
 289          return gmp_sub($x, $y);
 290      }
 291  
 292      function pow($base, $exponent)
 293      {
 294          return gmp_pow($base, $exponent);
 295      }
 296  
 297      function cmp($x, $y)
 298      {
 299          return gmp_cmp($x, $y);
 300      }
 301  
 302      function init($number, $base = 10)
 303      {
 304          return gmp_init($number, $base);
 305      }
 306  
 307      function mod($base, $modulus)
 308      {
 309          return gmp_mod($base, $modulus);
 310      }
 311  
 312      function mul($x, $y)
 313      {
 314          return gmp_mul($x, $y);
 315      }
 316  
 317      function div($x, $y)
 318      {
 319          return gmp_div_q($x, $y);
 320      }
 321  
 322      function powmod($base, $exponent, $modulus)
 323      {
 324          return gmp_powm($base, $exponent, $modulus);
 325      }
 326  
 327      function toString($num)
 328      {
 329          return gmp_strval($num);
 330      }
 331  }
 332  
 333  /**
 334   * Define the supported extensions.  An extension array has keys
 335   * 'modules', 'extension', and 'class'.  'modules' is an array of PHP
 336   * module names which the loading code will attempt to load.  These
 337   * values will be suffixed with a library file extension (e.g. ".so").
 338   * 'extension' is the name of a PHP extension which will be tested
 339   * before 'modules' are loaded.  'class' is the string name of a
 340   * {@link Auth_OpenID_MathWrapper} subclass which should be
 341   * instantiated if a given extension is present.
 342   *
 343   * You can define new math library implementations and add them to
 344   * this array.
 345   */
 346  function Auth_OpenID_math_extensions()
 347  {
 348      $result = array();
 349  
 350      if (!defined('Auth_OpenID_BUGGY_GMP')) {
 351          $result[] =
 352              array('modules' => array('gmp', 'php_gmp'),
 353                    'extension' => 'gmp',
 354                    'class' => 'Auth_OpenID_GmpMathWrapper');
 355      }
 356  
 357      $result[] = array(
 358                        'modules' => array('bcmath', 'php_bcmath'),
 359                        'extension' => 'bcmath',
 360                        'class' => 'Auth_OpenID_BcMathWrapper');
 361  
 362      return $result;
 363  }
 364  
 365  /**
 366   * Detect which (if any) math library is available
 367   */
 368  function Auth_OpenID_detectMathLibrary($exts)
 369  {
 370      $loaded = false;
 371  
 372      foreach ($exts as $extension) {
 373          // See if the extension specified is already loaded.
 374          if ($extension['extension'] &&
 375              extension_loaded($extension['extension'])) {
 376              $loaded = true;
 377          }
 378  
 379          // Try to load dynamic modules.
 380          if (!$loaded) {
 381              foreach ($extension['modules'] as $module) {
 382                  if (@dl($module . "." . PHP_SHLIB_SUFFIX)) {
 383                      $loaded = true;
 384                      break;
 385                  }
 386              }
 387          }
 388  
 389          // If the load succeeded, supply an instance of
 390          // Auth_OpenID_MathWrapper which wraps the specified
 391          // module's functionality.
 392          if ($loaded) {
 393              return $extension;
 394          }
 395      }
 396  
 397      return false;
 398  }
 399  
 400  /**
 401   * {@link Auth_OpenID_getMathLib} checks for the presence of long
 402   * number extension modules and returns an instance of
 403   * {@link Auth_OpenID_MathWrapper} which exposes the module's
 404   * functionality.
 405   *
 406   * Checks for the existence of an extension module described by the
 407   * result of {@link Auth_OpenID_math_extensions()} and returns an
 408   * instance of a wrapper for that extension module.  If no extension
 409   * module is found, an instance of {@link Auth_OpenID_MathWrapper} is
 410   * returned, which wraps the native PHP integer implementation.  The
 411   * proper calling convention for this method is $lib =&
 412   * Auth_OpenID_getMathLib().
 413   *
 414   * This function checks for the existence of specific long number
 415   * implementations in the following order: GMP followed by BCmath.
 416   *
 417   * @return Auth_OpenID_MathWrapper $instance An instance of
 418   * {@link Auth_OpenID_MathWrapper} or one of its subclasses
 419   *
 420   * @package OpenID
 421   */
 422  function &Auth_OpenID_getMathLib()
 423  {
 424      // The instance of Auth_OpenID_MathWrapper that we choose to
 425      // supply will be stored here, so that subseqent calls to this
 426      // method will return a reference to the same object.
 427      static $lib = null;
 428  
 429      if (isset($lib)) {
 430          return $lib;
 431      }
 432  
 433      if (Auth_OpenID_noMathSupport()) {
 434          $null = null;
 435          return $null;
 436      }
 437  
 438      // If this method has not been called before, look at
 439      // Auth_OpenID_math_extensions and try to find an extension that
 440      // works.
 441      $ext = Auth_OpenID_detectMathLibrary(Auth_OpenID_math_extensions());
 442      if ($ext === false) {
 443          $tried = array();
 444          foreach (Auth_OpenID_math_extensions() as $extinfo) {
 445              $tried[] = $extinfo['extension'];
 446          }
 447          $triedstr = implode(", ", $tried);
 448  
 449          Auth_OpenID_setNoMathSupport();
 450  
 451          $result = null;
 452          return $result;
 453      }
 454  
 455      // Instantiate a new wrapper
 456      $class = $ext['class'];
 457      $lib = new $class();
 458  
 459      return $lib;
 460  }
 461  
 462  function Auth_OpenID_setNoMathSupport()
 463  {
 464      if (!defined('Auth_OpenID_NO_MATH_SUPPORT')) {
 465          define('Auth_OpenID_NO_MATH_SUPPORT', true);
 466      }
 467  }
 468  
 469  function Auth_OpenID_noMathSupport()
 470  {
 471      return defined('Auth_OpenID_NO_MATH_SUPPORT');
 472  }
 473  
 474  ?>