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