Subversion Repositories oidplus

Rev

Rev 846 | Rev 1042 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  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.  
  16. namespace phpseclib3\Math\BigInteger\Engines\PHP\Reductions;
  17.  
  18. use phpseclib3\Math\BigInteger\Engines\PHP;
  19. use 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.  */
  28. abstract 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.