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 */
21require_once 'Auth/OpenID/CryptUtil.php';
22
23/**
24 * Need Auth_OpenID::bytes().
25 */
26require_once 'Auth/OpenID.php';
27
28/**
29 * The superclass of all big-integer math implementations
30 * @access private
31 * @package OpenID
32 */
33class 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 */
190class 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 */
276class 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 */
343function 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 */
364function 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 */
399function 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
439function Auth_OpenID_setNoMathSupport()
440{
441    if (!defined('Auth_OpenID_NO_MATH_SUPPORT')) {
442        define('Auth_OpenID_NO_MATH_SUPPORT', true);
443    }
444}
445
446function Auth_OpenID_noMathSupport()
447{
448    return defined('Auth_OpenID_NO_MATH_SUPPORT');
449}
450
451
452