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