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('modules' => array('bcmath', 'php_bcmath'),
355:                       'extension' => 'bcmath',
356:                       'class' => 'Auth_OpenID_BcMathWrapper');
357: 
358:     return $result;
359: }
360: 
361: /**
362:  * Detect which (if any) math library is available
363:  */
364: function Auth_OpenID_detectMathLibrary($exts)
365: {
366:     $loaded = false;
367: 
368:     foreach ($exts as $extension) {
369:         if (extension_loaded($extension['extension'])) {
370:             return $extension;
371:         }
372:     }
373: 
374:     return false;
375: }
376: 
377: /**
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
381:  * functionality.
382:  *
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().
390:  *
391:  * This function checks for the existence of specific long number
392:  * implementations in the following order: GMP followed by BCmath.
393:  *
394:  * @return Auth_OpenID_MathWrapper $instance An instance of
395:  * {@link Auth_OpenID_MathWrapper} or one of its subclasses
396:  *
397:  * @package OpenID
398:  */
399: function Auth_OpenID_getMathLib()
400: {
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.
404:     static $lib = null;
405: 
406:     if (isset($lib)) {
407:         return $lib;
408:     }
409: 
410:     if (Auth_OpenID_noMathSupport()) {
411:         $null = null;
412:         return $null;
413:     }
414: 
415:     // If this method has not been called before, look at
416:     // Auth_OpenID_math_extensions and try to find an extension that
417:     // works.
418:     $ext = Auth_OpenID_detectMathLibrary(Auth_OpenID_math_extensions());
419:     if ($ext === false) {
420:         $tried = array();
421:         foreach (Auth_OpenID_math_extensions() as $extinfo) {
422:             $tried[] = $extinfo['extension'];
423:         }
424:         $triedstr = implode(", ", $tried);
425: 
426:         Auth_OpenID_setNoMathSupport();
427: 
428:         $result = null;
429:         return $result;
430:     }
431: 
432:     // Instantiate a new wrapper
433:     $class = $ext['class'];
434:     $lib = new $class();
435: 
436:     return $lib;
437: }
438: 
439: function Auth_OpenID_setNoMathSupport()
440: {
441:     if (!defined('Auth_OpenID_NO_MATH_SUPPORT')) {
442:         define('Auth_OpenID_NO_MATH_SUPPORT', true);
443:     }
444: }
445: 
446: function Auth_OpenID_noMathSupport()
447: {
448:     return defined('Auth_OpenID_NO_MATH_SUPPORT');
449: }
450: 
451: 
452: