git.roojs.org Git - web.mtrack/blob - inc/lib/Auth/OpenID/BigMath.php

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