Rev 846 | Rev 1042 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
827 | daniel-mar | 1 | <?php |
2 | |||
3 | /** |
||
4 | * PHP Dynamic Barrett Modular Exponentiation Engine |
||
5 | * |
||
6 | * PHP version 5 and 7 |
||
7 | * |
||
874 | daniel-mar | 8 | * @category Math |
9 | * @package BigInteger |
||
827 | daniel-mar | 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 | * |
||
874 | daniel-mar | 24 | * @package PHP |
827 | daniel-mar | 25 | * @author Jim Wigginton <terrafrost@php.net> |
874 | daniel-mar | 26 | * @access public |
827 | daniel-mar | 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 | } |