[Summary view] [Print] [Text view]

   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 <[email protected]>
  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 <[email protected]>
  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  }