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