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