1<?php
2
3/**
4 * PHP Dynamic Barrett Modular Exponentiation Engine
5 *
6 * PHP version 5 and 7
7 *
8 * @category  Math
9 * @package   BigInteger
10 * @author    Jim Wigginton <terrafrost@php.net>
11 * @copyright 2017 Jim Wigginton
12 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
13 * @link      http://pear.php.net/package/Math_BigInteger
14 */
15
16namespace phpseclib3\Math\BigInteger\Engines\PHP\Reductions;
17
18use phpseclib3\Math\BigInteger\Engines\PHP\Base;
19use phpseclib3\Math\BigInteger\Engines\PHP;
20
21/**
22 * PHP Dynamic Barrett Modular Exponentiation Engine
23 *
24 * @package PHP
25 * @author  Jim Wigginton <terrafrost@php.net>
26 * @access  public
27 */
28abstract class EvalBarrett extends Base
29{
30    /**
31     * Custom Reduction Function
32     *
33     * @see self::generateCustomReduction
34     */
35    private static $custom_reduction;
36
37    /**
38     * Barrett Modular Reduction
39     *
40     * This calls a dynamically generated loop unrolled function that's specific to a given modulo.
41     * Array lookups are avoided as are if statements testing for how many bits the host OS supports, etc.
42     *
43     * @param array $n
44     * @param array $m
45     * @param string $class
46     * @return array
47     */
48    protected static function reduce(array $n, array $m, $class)
49    {
50        $inline = self::$custom_reduction;
51        return $inline($n);
52    }
53
54    /**
55     * Generate Custom Reduction
56     *
57     * @param PHP $m
58     * @param string $class
59     * @return callable
60     */
61    protected static function generateCustomReduction(PHP $m, $class)
62    {
63        if (isset($n->reduce)) {
64            self::$custom_reduction = $n->reduce;
65            return $n->reduce;
66        }
67
68        $m_length = count($m->value);
69
70        if ($m_length < 5) {
71            $code = '
72                $lhs = new ' . $class . '();
73                $lhs->value = $x;
74                $rhs = new ' . $class . '();
75                $rhs->value = [' .
76                implode(',', array_map('self::float2string', $m->value)) . '];
77                list(, $temp) = $lhs->divide($rhs);
78                return $temp->value;
79            ';
80            eval('$func = function ($x) { ' . $code . '};');
81            self::$custom_reduction = $func;
82            //self::$custom_reduction = \Closure::bind($func, $m, $class);
83            return $func;
84        }
85
86        $lhs = new $class();
87        $lhs_value = &$lhs->value;
88
89        $lhs_value = self::array_repeat(0, $m_length + ($m_length >> 1));
90        $lhs_value[] = 1;
91        $rhs = new $class();
92
93        list($u, $m1) = $lhs->divide($m);
94
95        if ($class::BASE != 26) {
96            $u = $u->value;
97        } else {
98            $lhs_value = self::array_repeat(0, 2 * $m_length);
99            $lhs_value[] = 1;
100            $rhs = new $class();
101
102            list($u) = $lhs->divide($m);
103            $u = $u->value;
104        }
105
106        $m = $m->value;
107        $m1 = $m1->value;
108
109        $cutoff = count($m) + (count($m) >> 1);
110
111        $code = '
112            if (count($n) > ' . (2 * count($m)) . ') {
113                $lhs = new ' . $class . '();
114                $rhs = new ' . $class . '();
115                $lhs->value = $n;
116                $rhs->value = [' .
117                implode(',', array_map('self::float2string', $m)) . '];
118                list(, $temp) = $lhs->divide($rhs);
119                return $temp->value;
120            }
121
122            $lsd = array_slice($n, 0, ' . $cutoff . ');
123            $msd = array_slice($n, ' . $cutoff . ');';
124
125        $code.= self::generateInlineTrim('msd');
126        $code.= self::generateInlineMultiply('msd', $m1, 'temp', $class);
127        $code.= self::generateInlineAdd('lsd', 'temp', 'n', $class);
128
129        $code.= '$temp = array_slice($n, ' . (count($m) - 1) . ');';
130        $code.= self::generateInlineMultiply('temp', $u, 'temp2', $class);
131        $code.= self::generateInlineTrim('temp2');
132
133        $code.= $class::BASE == 26 ?
134            '$temp = array_slice($temp2, ' . (count($m) + 1) . ');' :
135            '$temp = array_slice($temp2, ' . ((count($m) >> 1) + 1) . ');';
136        $code.= self::generateInlineMultiply('temp', $m, 'temp2', $class);
137        $code.= self::generateInlineTrim('temp2');
138
139        /*
140        if ($class::BASE == 26) {
141            $code.= '$n = array_slice($n, 0, ' . (count($m) + 1) . ');
142                     $temp2 = array_slice($temp2, 0, ' . (count($m) + 1) . ');';
143        }
144        */
145
146        $code.= self::generateInlineSubtract2('n', 'temp2', 'temp', $class);
147
148        $subcode = self::generateInlineSubtract1('temp', $m, 'temp2', $class);
149        $subcode.= '$temp = $temp2;';
150
151        $code.= self::generateInlineCompare($m, 'temp', $subcode);
152
153        $code.= 'return $temp;';
154
155        eval('$func = function ($n) { ' . $code . '};');
156
157        self::$custom_reduction = $func;
158
159        return $func;
160
161        //self::$custom_reduction = \Closure::bind($func, $m, $class);
162    }
163
164    /**
165     * Inline Trim
166     *
167     * Removes leading zeros
168     *
169     * @param string $name
170     * @return string
171     */
172    private static function generateInlineTrim($name)
173    {
174        return '
175            for ($i = count($' . $name . ') - 1; $i >= 0; --$i) {
176                if ($' . $name . '[$i]) {
177                    break;
178                }
179                unset($' . $name . '[$i]);
180            }';
181    }
182
183    /**
184     * Inline Multiply (unknown, known)
185     *
186     * @param string $input
187     * @param array $arr
188     * @param string $output
189     * @param string $class
190     * @return string
191     */
192    private static function generateInlineMultiply($input, array $arr, $output, $class)
193    {
194        if (!count($arr)) {
195            return 'return [];';
196        }
197
198        $regular = '
199            $length = count($' . $input . ');
200            if (!$length) {
201                $' . $output . ' = [];
202            }else{
203            $' . $output . ' = array_fill(0, $length + ' . count($arr) . ', 0);
204            $carry = 0;';
205
206            for ($i = 0; $i < count($arr); $i++) {
207            $regular.= '
208                $subtemp = $' . $input . '[0] * ' . $arr[$i];
209            $regular.= $i ? ' + $carry;' : ';';
210
211            $regular.= '$carry = ';
212            $regular.= $class::BASE === 26 ?
213                'intval($subtemp / 0x4000000);' :
214                '$subtemp >> 31;';
215            $regular.=
216                '$' . $output . '[' . $i . '] = ';
217            if ($class::BASE === 26) {
218                $regular.= '(int) (';
219            }
220            $regular.= '$subtemp - ' . $class::BASE_FULL . ' * $carry';
221            $regular.= $class::BASE === 26 ? ');' : ';';
222        }
223
224        $regular.= '$' . $output . '[' . count($arr) . '] = $carry;';
225
226        $regular.= '
227            for ($i = 1; $i < $length; ++$i) {';
228
229        for ($j = 0; $j < count($arr); $j++) {
230            $regular.= $j ? '$k++;' : '$k = $i;';
231            $regular.= '
232                $subtemp = $' . $output . '[$k] + $' . $input . '[$i] * ' . $arr[$j];
233            $regular.= $j ? ' + $carry;' : ';';
234
235            $regular.= '$carry = ';
236            $regular.= $class::BASE === 26 ?
237                'intval($subtemp / 0x4000000);' :
238                '$subtemp >> 31;';
239            $regular.=
240                '$' . $output . '[$k] = ';
241            if ($class::BASE === 26) {
242                $regular.= '(int) (';
243            }
244            $regular.= '$subtemp - ' . $class::BASE_FULL . ' * $carry';
245            $regular.= $class::BASE === 26 ? ');' : ';';
246        }
247
248        $regular.= '$' . $output. '[++$k] = $carry; $carry = 0;';
249
250        $regular.= '}}';
251
252        //if (count($arr) < 2 * self::KARATSUBA_CUTOFF) {
253        //}
254
255        return $regular;
256    }
257
258    /**
259     * Inline Addition
260     *
261     * @param string $x
262     * @param string $y
263     * @param string $result
264     * @param string $class
265     * @return string
266     */
267    private static function generateInlineAdd($x, $y, $result, $class)
268    {
269        $code = '
270            $length = max(count($' . $x . '), count($' . $y . '));
271            $' . $result . ' = array_pad($' . $x . ', $length + 1, 0);
272            $_' . $y . ' = array_pad($' . $y . ', $length, 0);
273            $carry = 0;
274            for ($i = 0, $j = 1; $j < $length; $i+=2, $j+=2) {
275                $sum = ($' . $result . '[$j] + $_' . $y . '[$j]) * ' . $class::BASE_FULL . '
276                           + $' . $result . '[$i] + $_' . $y . '[$i] +
277                           $carry;
278                $carry = $sum >= ' . self::float2string($class::MAX_DIGIT2) . ';
279                $sum = $carry ? $sum - ' . self::float2string($class::MAX_DIGIT2) . ' : $sum;';
280
281            $code.= $class::BASE === 26 ?
282                '$upper = intval($sum / 0x4000000); $' . $result . '[$i] = (int) ($sum - ' . $class::BASE_FULL . ' * $upper);' :
283                '$upper = $sum >> 31; $' . $result . '[$i] = $sum - ' . $class::BASE_FULL . ' * $upper;';
284            $code.= '
285                $' . $result . '[$j] = $upper;
286            }
287            if ($j == $length) {
288                $sum = $' . $result . '[$i] + $_' . $y . '[$i] + $carry;
289                $carry = $sum >= ' . self::float2string($class::BASE_FULL) . ';
290                $' . $result . '[$i] = $carry ? $sum - ' . self::float2string($class::BASE_FULL) . ' : $sum;
291            }
292            if ($carry) {
293                for (; $' . $result . '[$i] == ' . $class::MAX_DIGIT . '; ++$i) {
294                    $' . $result . '[$i] = 0;
295                }
296                ++$' . $result . '[$i];
297            }';
298            $code.= self::generateInlineTrim($result);
299
300            return $code;
301    }
302
303    /**
304     * Inline Subtraction 2
305     *
306     * For when $known is more digits than $unknown. This is the harder use case to optimize for.
307     *
308     * @param string $known
309     * @param string $unknown
310     * @param string $result
311     * @param string $class
312     * @return string
313     */
314    private static function generateInlineSubtract2($known, $unknown, $result, $class)
315    {
316        $code = '
317            $' . $result .' = $' . $known . ';
318            $carry = 0;
319            $size = count($' . $unknown . ');
320            for ($i = 0, $j = 1; $j < $size; $i+= 2, $j+= 2) {
321                $sum = ($' . $known . '[$j] - $' . $unknown . '[$j]) * ' . $class::BASE_FULL . ' + $' . $known . '[$i]
322                    - $' . $unknown . '[$i]
323                    - $carry;
324                $carry = $sum < 0;
325                if ($carry) {
326                    $sum+= ' . self::float2string($class::MAX_DIGIT2) . ';
327                }
328                $subtemp = ';
329        $code.= $class::BASE === 26 ?
330            'intval($sum / 0x4000000);' :
331            '$sum >> 31;';
332        $code.= '$' . $result . '[$i] = ';
333        if ($class::BASE === 26) {
334            $code.= '(int) (';
335        }
336        $code.= '$sum - ' . $class::BASE_FULL . ' * $subtemp';
337        if ($class::BASE === 26) {
338            $code.= ')';
339        }
340        $code.= ';
341                $' . $result . '[$j] = $subtemp;
342            }
343            if ($j == $size) {
344                $sum = $' . $known . '[$i] - $' . $unknown . '[$i] - $carry;
345                $carry = $sum < 0;
346                $' . $result . '[$i] = $carry ? $sum + ' . $class::BASE_FULL . ' : $sum;
347                ++$i;
348            }
349
350            if ($carry) {
351                for (; !$' . $result . '[$i]; ++$i) {
352                    $' . $result . '[$i] = ' . $class::MAX_DIGIT . ';
353                }
354                --$' . $result . '[$i];
355            }';
356
357        $code.= self::generateInlineTrim($result);
358
359        return $code;
360    }
361
362    /**
363     * Inline Subtraction 1
364     *
365     * For when $unknown is more digits than $known. This is the easier use case to optimize for.
366     *
367     * @param string $unknown
368     * @param array $known
369     * @param string $result
370     * @param string $class
371     * @return string
372     */
373    private static function generateInlineSubtract1($unknown, array $known, $result, $class)
374    {
375        $code = '$' . $result . ' = $' . $unknown . ';';
376        for ($i = 0, $j = 1; $j < count($known); $i+=2, $j+=2) {
377            $code.= '$sum = $' . $unknown . '[' . $j . '] * ' . $class::BASE_FULL . ' + $' . $unknown . '[' . $i . '] - ';
378            $code.= self::float2string($known[$j] * $class::BASE_FULL + $known[$i]);
379            if ($i != 0) {
380                $code.= ' - $carry';
381            }
382
383            $code.= ';
384                if ($carry = $sum < 0) {
385                    $sum+= ' . self::float2string($class::MAX_DIGIT2) . ';
386                }
387                $subtemp = ';
388            $code.= $class::BASE === 26 ?
389                'intval($sum / 0x4000000);' :
390                '$sum >> 31;';
391            $code.= '
392                $' . $result . '[' . $i . '] = ';
393            if ($class::BASE === 26) {
394                $code.= ' (int) (';
395            }
396            $code.= '$sum - ' . $class::BASE_FULL . ' * $subtemp';
397            if ($class::BASE === 26) {
398                $code.= ')';
399            }
400            $code.= ';
401                $' . $result . '[' . $j . '] = $subtemp;';
402        }
403
404        $code.= '$i = ' . $i . ';';
405
406        if ($j == count($known)) {
407            $code.= '
408                $sum = $' . $unknown . '[' . $i . '] - ' . $known[$i] . ' - $carry;
409                $carry = $sum < 0;
410                $' . $result . '[' . $i . '] = $carry ? $sum + ' . $class::BASE_FULL . ' : $sum;
411                ++$i;';
412        }
413
414        $code.= '
415            if ($carry) {
416                for (; !$' . $result . '[$i]; ++$i) {
417                    $' . $result . '[$i] = ' . $class::MAX_DIGIT . ';
418                }
419                --$' . $result . '[$i];
420            }';
421        $code.= self::generateInlineTrim($result);
422
423        return $code;
424    }
425
426    /**
427     * Inline Comparison
428     *
429     * If $unknown >= $known then loop
430     *
431     * @param array $known
432     * @param string $unknown
433     * @param string $subcode
434     * @return string
435     */
436    private static function generateInlineCompare(array $known, $unknown, $subcode)
437    {
438        $uniqid = uniqid();
439        $code = 'loop_' . $uniqid . ':
440            $clength = count($' . $unknown . ');
441            switch (true) {
442                case $clength < ' . count($known) . ':
443                    goto end_' . $uniqid . ';
444                case $clength > ' . count($known) . ':';
445        for ($i = count($known) - 1; $i >= 0; $i--) {
446            $code.= '
447                case $' . $unknown . '[' . $i . '] > ' . $known[$i] . ':
448                    goto subcode_' . $uniqid . ';
449                case $' . $unknown . '[' . $i . '] < ' . $known[$i] . ':
450                    goto end_' . $uniqid . ';';
451        }
452        $code.= '
453                default:
454                    // do subcode
455            }
456
457            subcode_' . $uniqid . ':' . $subcode . '
458            goto loop_' . $uniqid . ';
459
460            end_' . $uniqid . ':';
461
462        return $code;
463    }
464
465    /**
466     * Convert a float to a string
467     *
468     * If you do echo floatval(pow(2, 52)) you'll get 4.6116860184274E+18. It /can/ be displayed without a loss of
469     * precision but displayed in this way there will be precision loss, hence the need for this method.
470     *
471     * @param int|float $num
472     * @return string
473     */
474    private static function float2string($num)
475    {
476        if (!is_float($num)) {
477            return $num;
478        }
479
480        if ($num < 0) {
481            return '-' . self::float2string(abs($num));
482        }
483
484        $temp = '';
485        while ($num) {
486            $temp = fmod($num, 10) . $temp;
487            $num = floor($num / 10);
488        }
489
490        return $temp;
491    }
492}