1<?php
2
3/**
4 * BCMath 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\BCMath\Reductions;
17
18use phpseclib3\Math\BigInteger\Engines\BCMath;
19use phpseclib3\Math\BigInteger\Engines\BCMath\Base;
20
21/**
22 * PHP 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 string $n
44     * @param string $m
45     * @return string
46     */
47    protected static function reduce($n, $m)
48    {
49        $inline = self::$custom_reduction;
50        return $inline($n);
51    }
52
53    /**
54     * Generate Custom Reduction
55     *
56     * @param BCMath $m
57     * @param string $class
58     * @return callable|void
59     */
60    protected static function generateCustomReduction(BCMath $m, $class)
61    {
62        $m_length = strlen($m);
63
64        if ($m_length < 5) {
65            $code = 'return bcmod($x, $n);';
66            eval('$func = function ($n) { ' . $code . '};');
67            self::$custom_reduction = $func;
68            return;
69        }
70
71        $lhs = '1' . str_repeat('0', $m_length + ($m_length >> 1));
72        $u = bcdiv($lhs, $m, 0);
73        $m1 = bcsub($lhs, bcmul($u, $m));
74
75        $cutoff = $m_length + ($m_length >> 1);
76
77        $m = "'$m'";
78        $u = "'$u'";
79        $m1 = "'$m1'";
80
81        $code = '
82            $lsd = substr($n, -' . $cutoff . ');
83            $msd = substr($n, 0, -' . $cutoff . ');
84
85            $temp = bcmul($msd, ' . $m1 . ');
86            $n = bcadd($lsd, $temp);
87
88            $temp = substr($n, 0, ' . (-$m_length + 1) . ');
89            $temp = bcmul($temp, ' . $u . ');
90            $temp = substr($temp, 0, ' . (-($m_length >> 1) - 1) . ');
91            $temp = bcmul($temp, ' . $m . ');
92
93            $result = bcsub($n, $temp);
94
95            if ($result[0] == \'-\') {
96                $temp = \'1' . str_repeat('0', $m_length + 1) . '\';
97                $result = bcadd($result, $temp);
98            }
99
100            while (bccomp($result, ' . $m . ') >= 0) {
101                $result = bcsub($result, ' . $m . ');
102            }
103
104            return $result;';
105
106        eval('$func = function ($n) { ' . $code . '};');
107
108        self::$custom_reduction = $func;
109
110        return $func;
111    }
112}
113