4 * BigMath: A math library wrapper that abstracts out the underlying
5 * long integer library.
9 * LICENSE: See the COPYING file included in this distribution.
13 * @author JanRain, Inc. <openid@janrain.com>
14 * @copyright 2005-2008 Janrain, Inc.
15 * @license http://www.apache.org/licenses/LICENSE-2.0 Apache
19 * Needed for random number generation
21 require_once 'Auth/OpenID/CryptUtil.php';
24 * Need Auth_OpenID::bytes().
26 require_once 'Auth/OpenID.php';
29 * The superclass of all big-integer math implementations
33 class Auth_OpenID_MathLibrary {
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
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
43 * @return string $binary The binary version of $long
45 function longToBinary($long)
47 $cmp = $this->cmp($long, 0);
49 $msg = __FUNCTION__ . " takes only positive integers.";
50 trigger_error($msg, E_USER_ERROR);
60 while ($this->cmp($long, 0) > 0) {
61 array_unshift($bytes, $this->mod($long, 256));
62 $long = $this->div($long, pow(2, 8));
65 if ($bytes && ($bytes[0] > 127)) {
66 array_unshift($bytes, 0);
70 foreach ($bytes as $byte) {
71 $string .= pack('C', $byte);
78 * Given a binary string, returns the binary string converted to a
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
86 function binaryToLong($str)
92 // Use array_merge to return a zero-indexed array instead of a
94 $bytes = array_merge(unpack('C*', $str));
98 if ($bytes && ($bytes[0] > 127)) {
99 trigger_error("bytesToNum works only for positive integers.",
104 foreach ($bytes as $byte) {
105 $n = $this->mul($n, pow(2, 8));
106 $n = $this->add($n, $byte);
112 function base64ToLong($str)
114 $b64 = base64_decode($str);
116 if ($b64 === false) {
120 return $this->binaryToLong($b64);
123 function longToBase64($str)
125 return base64_encode($this->longToBinary($str));
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
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
144 static $duplicate_cache = array();
146 // Used as the key for the duplicate cache
147 $rbytes = $this->longToBinary($stop);
149 if (array_key_exists($rbytes, $duplicate_cache)) {
150 list($duplicate, $nbytes) = $duplicate_cache[$rbytes];
152 if ($rbytes[0] == "\x00") {
153 $nbytes = Auth_OpenID::bytes($rbytes) - 1;
155 $nbytes = Auth_OpenID::bytes($rbytes);
158 $mxrand = $this->pow(256, $nbytes);
160 // If we get a number less than this, then it is in the
162 $duplicate = $this->mod($mxrand, $stop);
164 if (count($duplicate_cache) > 10) {
165 $duplicate_cache = array();
168 $duplicate_cache[$rbytes] = array($duplicate, $nbytes);
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);
177 return $this->mod($n, $stop);
182 * Exposes BCmath math library functionality.
184 * {@link Auth_OpenID_BcMathWrapper} wraps the functionality provided
185 * by the BCMath extension.
190 class Auth_OpenID_BcMathWrapper extends Auth_OpenID_MathLibrary{
191 var $type = 'bcmath';
195 return bcadd($x, $y);
200 return bcsub($x, $y);
203 function pow($base, $exponent)
205 return bcpow($base, $exponent);
210 return bccomp($x, $y);
213 function init($number, $base = 10)
218 function mod($base, $modulus)
220 return bcmod($base, $modulus);
225 return bcmul($x, $y);
230 return bcdiv($x, $y);
234 * Same as bcpowmod when bcpowmod is missing
238 function _powmod($base, $exponent, $modulus)
240 $square = $this->mod($base, $modulus);
242 while($this->cmp($exponent, 0) > 0) {
243 if ($this->mod($exponent, 2)) {
244 $result = $this->mod($this->mul($result, $square), $modulus);
246 $square = $this->mod($this->mul($square, $square), $modulus);
247 $exponent = $this->div($exponent, 2);
252 function powmod($base, $exponent, $modulus)
254 if (function_exists('bcpowmod')) {
255 return bcpowmod($base, $exponent, $modulus);
257 return $this->_powmod($base, $exponent, $modulus);
261 function toString($num)
268 * Exposes GMP math library functionality.
270 * {@link Auth_OpenID_GmpMathWrapper} wraps the functionality provided
271 * by the GMP extension.
276 class Auth_OpenID_GmpMathWrapper extends Auth_OpenID_MathLibrary{
281 return gmp_add($x, $y);
286 return gmp_sub($x, $y);
289 function pow($base, $exponent)
291 return gmp_pow($base, $exponent);
296 return gmp_cmp($x, $y);
299 function init($number, $base = 10)
301 return gmp_init($number, $base);
304 function mod($base, $modulus)
306 return gmp_mod($base, $modulus);
311 return gmp_mul($x, $y);
316 return gmp_div_q($x, $y);
319 function powmod($base, $exponent, $modulus)
321 return gmp_powm($base, $exponent, $modulus);
324 function toString($num)
326 return gmp_strval($num);
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.
340 * You can define new math library implementations and add them to
343 function Auth_OpenID_math_extensions()
347 if (!defined('Auth_OpenID_BUGGY_GMP')) {
349 array('modules' => array('gmp', 'php_gmp'),
350 'extension' => 'gmp',
351 'class' => 'Auth_OpenID_GmpMathWrapper');
354 $result[] = array('modules' => array('bcmath', 'php_bcmath'),
355 'extension' => 'bcmath',
356 'class' => 'Auth_OpenID_BcMathWrapper');
362 * Detect which (if any) math library is available
364 function Auth_OpenID_detectMathLibrary($exts)
368 foreach ($exts as $extension) {
369 if (extension_loaded($extension['extension'])) {
378 * {@link Auth_OpenID_getMathLib} checks for the presence of long
379 * number extension modules and returns an instance of
380 * {@link Auth_OpenID_MathWrapper} which exposes the module's
383 * Checks for the existence of an extension module described by the
384 * result of {@link Auth_OpenID_math_extensions()} and returns an
385 * instance of a wrapper for that extension module. If no extension
386 * module is found, an instance of {@link Auth_OpenID_MathWrapper} is
387 * returned, which wraps the native PHP integer implementation. The
388 * proper calling convention for this method is $lib =
389 * Auth_OpenID_getMathLib().
391 * This function checks for the existence of specific long number
392 * implementations in the following order: GMP followed by BCmath.
394 * @return Auth_OpenID_MathWrapper $instance An instance of
395 * {@link Auth_OpenID_MathWrapper} or one of its subclasses
399 function Auth_OpenID_getMathLib()
401 // The instance of Auth_OpenID_MathWrapper that we choose to
402 // supply will be stored here, so that subseqent calls to this
403 // method will return a reference to the same object.
410 if (Auth_OpenID_noMathSupport()) {
415 // If this method has not been called before, look at
416 // Auth_OpenID_math_extensions and try to find an extension that
418 $ext = Auth_OpenID_detectMathLibrary(Auth_OpenID_math_extensions());
419 if ($ext === false) {
421 foreach (Auth_OpenID_math_extensions() as $extinfo) {
422 $tried[] = $extinfo['extension'];
424 $triedstr = implode(", ", $tried);
426 Auth_OpenID_setNoMathSupport();
432 // Instantiate a new wrapper
433 $class = $ext['class'];
439 function Auth_OpenID_setNoMathSupport()
441 if (!defined('Auth_OpenID_NO_MATH_SUPPORT')) {
442 define('Auth_OpenID_NO_MATH_SUPPORT', true);
446 function Auth_OpenID_noMathSupport()
448 return defined('Auth_OpenID_NO_MATH_SUPPORT');