defender-security / lib / packages / Brick / Math / Internal / Calculator / NativeCalculator.php

NativeCalculator.php in Defender Security – Malware Scanner, Login Security & Firewall 6.3.0, at lib/packages/Brick/Math/Internal/Calculator/NativeCalculator.php

635 lines 14.5 KB

Raw Download Zip

1	<?php
2
3	declare(strict_types=1);
4
5	namespace WP_DEFENDER_VENDOR\Brick\Math\Internal\Calculator;
6
7	use WP_DEFENDER_VENDOR\Brick\Math\Internal\Calculator;
8
9	/**
10	* Calculator implementation using only native PHP code.
11	*
12	* @internal
13	*
14	* @psalm-immutable
15	*/
16	class NativeCalculator extends Calculator
17	{
18	/**
19	* The max number of digits the platform can natively add, subtract, multiply or divide without overflow.
20	* For multiplication, this represents the max sum of the lengths of both operands.
21	*
22	* For addition, it is assumed that an extra digit can hold a carry (1) without overflowing.
23	* Example: 32-bit: max number 1,999,999,999 (9 digits + carry)
24	* 64-bit: max number 1,999,999,999,999,999,999 (18 digits + carry)
25	*
26	* @var int
27	*/
28	private $maxDigits;
29
30	/**
31	* Class constructor.
32	*
33	* @codeCoverageIgnore
34	*/
35	public function __construct()
36	{
37	switch (PHP_INT_SIZE) {
38	case 4:
39	$this->maxDigits = 9;
40	break;
41
42	case 8:
43	$this->maxDigits = 18;
44	break;
45
46	default:
47	throw new \RuntimeException('The platform is not 32-bit or 64-bit as expected.');
48	}
49	}
50
51	/**
52	* {@inheritdoc}
53	*/
54	public function add(string $a, string $b) : string
55	{
56	/**
57	* @psalm-var numeric-string $a
58	* @psalm-var numeric-string $b
59	*/
60	$result = $a + $b;
61
62	if (is_int($result)) {
63	return (string) $result;
64	}
65
66	if ($a === '0') {
67	return $b;
68	}
69
70	if ($b === '0') {
71	return $a;
72	}
73
74	[$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b);
75
76	$result = $aNeg === $bNeg ? $this->doAdd($aDig, $bDig) : $this->doSub($aDig, $bDig);
77
78	if ($aNeg) {
79	$result = $this->neg($result);
80	}
81
82	return $result;
83	}
84
85	/**
86	* {@inheritdoc}
87	*/
88	public function sub(string $a, string $b) : string
89	{
90	return $this->add($a, $this->neg($b));
91	}
92
93	/**
94	* {@inheritdoc}
95	*/
96	public function mul(string $a, string $b) : string
97	{
98	/**
99	* @psalm-var numeric-string $a
100	* @psalm-var numeric-string $b
101	*/
102	$result = $a * $b;
103
104	if (is_int($result)) {
105	return (string) $result;
106	}
107
108	if ($a === '0' \|\| $b === '0') {
109	return '0';
110	}
111
112	if ($a === '1') {
113	return $b;
114	}
115
116	if ($b === '1') {
117	return $a;
118	}
119
120	if ($a === '-1') {
121	return $this->neg($b);
122	}
123
124	if ($b === '-1') {
125	return $this->neg($a);
126	}
127
128	[$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b);
129
130	$result = $this->doMul($aDig, $bDig);
131
132	if ($aNeg !== $bNeg) {
133	$result = $this->neg($result);
134	}
135
136	return $result;
137	}
138
139	/**
140	* {@inheritdoc}
141	*/
142	public function divQ(string $a, string $b) : string
143	{
144	return $this->divQR($a, $b)[0];
145	}
146
147	/**
148	* {@inheritdoc}
149	*/
150	public function divR(string $a, string $b): string
151	{
152	return $this->divQR($a, $b)[1];
153	}
154
155	/**
156	* {@inheritdoc}
157	*/
158	public function divQR(string $a, string $b) : array
159	{
160	if ($a === '0') {
161	return ['0', '0'];
162	}
163
164	if ($a === $b) {
165	return ['1', '0'];
166	}
167
168	if ($b === '1') {
169	return [$a, '0'];
170	}
171
172	if ($b === '-1') {
173	return [$this->neg($a), '0'];
174	}
175
176	/** @psalm-var numeric-string $a */
177	$na = $a * 1; // cast to number
178
179	if (is_int($na)) {
180	/** @psalm-var numeric-string $b */
181	$nb = $b * 1;
182
183	if (is_int($nb)) {
184	// the only division that may overflow is PHP_INT_MIN / -1,
185	// which cannot happen here as we've already handled a divisor of -1 above.
186	$r = $na % $nb;
187	$q = ($na - $r) / $nb;
188
189	assert(is_int($q));
190
191	return [
192	(string) $q,
193	(string) $r
194	];
195	}
196	}
197
198	[$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b);
199
200	[$q, $r] = $this->doDiv($aDig, $bDig);
201
202	if ($aNeg !== $bNeg) {
203	$q = $this->neg($q);
204	}
205
206	if ($aNeg) {
207	$r = $this->neg($r);
208	}
209
210	return [$q, $r];
211	}
212
213	/**
214	* {@inheritdoc}
215	*/
216	public function pow(string $a, int $e) : string
217	{
218	if ($e === 0) {
219	return '1';
220	}
221
222	if ($e === 1) {
223	return $a;
224	}
225
226	$odd = $e % 2;
227	$e -= $odd;
228
229	$aa = $this->mul($a, $a);
230
231	/** @psalm-suppress PossiblyInvalidArgument We're sure that $e / 2 is an int now */
232	$result = $this->pow($aa, $e / 2);
233
234	if ($odd === 1) {
235	$result = $this->mul($result, $a);
236	}
237
238	return $result;
239	}
240
241	/**
242	* Algorithm from: https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/
243	*
244	* {@inheritdoc}
245	*/
246	public function modPow(string $base, string $exp, string $mod) : string
247	{
248	// special case: the algorithm below fails with 0 power 0 mod 1 (returns 1 instead of 0)
249	if ($base === '0' && $exp === '0' && $mod === '1') {
250	return '0';
251	}
252
253	// special case: the algorithm below fails with power 0 mod 1 (returns 1 instead of 0)
254	if ($exp === '0' && $mod === '1') {
255	return '0';
256	}
257
258	$x = $base;
259
260	$res = '1';
261
262	// numbers are positive, so we can use remainder instead of modulo
263	$x = $this->divR($x, $mod);
264
265	while ($exp !== '0') {
266	if (in_array($exp[-1], ['1', '3', '5', '7', '9'])) { // odd
267	$res = $this->divR($this->mul($res, $x), $mod);
268	}
269
270	$exp = $this->divQ($exp, '2');
271	$x = $this->divR($this->mul($x, $x), $mod);
272	}
273
274	return $res;
275	}
276
277	/**
278	* Adapted from https://cp-algorithms.com/num_methods/roots_newton.html
279	*
280	* {@inheritDoc}
281	*/
282	public function sqrt(string $n) : string
283	{
284	if ($n === '0') {
285	return '0';
286	}
287
288	// initial approximation
289	$x = \str_repeat('9', \intdiv(\strlen($n), 2) ?: 1);
290
291	$decreased = false;
292
293	for (;;) {
294	$nx = $this->divQ($this->add($x, $this->divQ($n, $x)), '2');
295
296	if ($x === $nx \|\| $this->cmp($nx, $x) > 0 && $decreased) {
297	break;
298	}
299
300	$decreased = $this->cmp($nx, $x) < 0;
301	$x = $nx;
302	}
303
304	return $x;
305	}
306
307	/**
308	* Performs the addition of two non-signed large integers.
309	*
310	* @param string $a The first operand.
311	* @param string $b The second operand.
312	*
313	* @return string
314	*/
315	private function doAdd(string $a, string $b) : string
316	{
317	[$a, $b, $length] = $this->pad($a, $b);
318
319	$carry = 0;
320	$result = '';
321
322	for ($i = $length - $this->maxDigits;; $i -= $this->maxDigits) {
323	$blockLength = $this->maxDigits;
324
325	if ($i < 0) {
326	$blockLength += $i;
327	/** @psalm-suppress LoopInvalidation */
328	$i = 0;
329	}
330
331	/** @psalm-var numeric-string $blockA */
332	$blockA = \substr($a, $i, $blockLength);
333
334	/** @psalm-var numeric-string $blockB */
335	$blockB = \substr($b, $i, $blockLength);
336
337	$sum = (string) ($blockA + $blockB + $carry);
338	$sumLength = \strlen($sum);
339
340	if ($sumLength > $blockLength) {
341	$sum = \substr($sum, 1);
342	$carry = 1;
343	} else {
344	if ($sumLength < $blockLength) {
345	$sum = \str_repeat('0', $blockLength - $sumLength) . $sum;
346	}
347	$carry = 0;
348	}
349
350	$result = $sum . $result;
351
352	if ($i === 0) {
353	break;
354	}
355	}
356
357	if ($carry === 1) {
358	$result = '1' . $result;
359	}
360
361	return $result;
362	}
363
364	/**
365	* Performs the subtraction of two non-signed large integers.
366	*
367	* @param string $a The first operand.
368	* @param string $b The second operand.
369	*
370	* @return string
371	*/
372	private function doSub(string $a, string $b) : string
373	{
374	if ($a === $b) {
375	return '0';
376	}
377
378	// Ensure that we always subtract to a positive result: biggest minus smallest.
379	$cmp = $this->doCmp($a, $b);
380
381	$invert = ($cmp === -1);
382
383	if ($invert) {
384	$c = $a;
385	$a = $b;
386	$b = $c;
387	}
388
389	[$a, $b, $length] = $this->pad($a, $b);
390
391	$carry = 0;
392	$result = '';
393
394	$complement = 10 ** $this->maxDigits;
395
396	for ($i = $length - $this->maxDigits;; $i -= $this->maxDigits) {
397	$blockLength = $this->maxDigits;
398
399	if ($i < 0) {
400	$blockLength += $i;
401	/** @psalm-suppress LoopInvalidation */
402	$i = 0;
403	}
404
405	/** @psalm-var numeric-string $blockA */
406	$blockA = \substr($a, $i, $blockLength);
407
408	/** @psalm-var numeric-string $blockB */
409	$blockB = \substr($b, $i, $blockLength);
410
411	$sum = $blockA - $blockB - $carry;
412
413	if ($sum < 0) {
414	$sum += $complement;
415	$carry = 1;
416	} else {
417	$carry = 0;
418	}
419
420	$sum = (string) $sum;
421	$sumLength = \strlen($sum);
422
423	if ($sumLength < $blockLength) {
424	$sum = \str_repeat('0', $blockLength - $sumLength) . $sum;
425	}
426
427	$result = $sum . $result;
428
429	if ($i === 0) {
430	break;
431	}
432	}
433
434	// Carry cannot be 1 when the loop ends, as a > b
435	assert($carry === 0);
436
437	$result = \ltrim($result, '0');
438
439	if ($invert) {
440	$result = $this->neg($result);
441	}
442
443	return $result;
444	}
445
446	/**
447	* Performs the multiplication of two non-signed large integers.
448	*
449	* @param string $a The first operand.
450	* @param string $b The second operand.
451	*
452	* @return string
453	*/
454	private function doMul(string $a, string $b) : string
455	{
456	$x = \strlen($a);
457	$y = \strlen($b);
458
459	$maxDigits = \intdiv($this->maxDigits, 2);
460	$complement = 10 ** $maxDigits;
461
462	$result = '0';
463
464	for ($i = $x - $maxDigits;; $i -= $maxDigits) {
465	$blockALength = $maxDigits;
466
467	if ($i < 0) {
468	$blockALength += $i;
469	/** @psalm-suppress LoopInvalidation */
470	$i = 0;
471	}
472
473	$blockA = (int) \substr($a, $i, $blockALength);
474
475	$line = '';
476	$carry = 0;
477
478	for ($j = $y - $maxDigits;; $j -= $maxDigits) {
479	$blockBLength = $maxDigits;
480
481	if ($j < 0) {
482	$blockBLength += $j;
483	/** @psalm-suppress LoopInvalidation */
484	$j = 0;
485	}
486
487	$blockB = (int) \substr($b, $j, $blockBLength);
488
489	$mul = $blockA * $blockB + $carry;
490	$value = $mul % $complement;
491	$carry = ($mul - $value) / $complement;
492
493	$value = (string) $value;
494	$value = \str_pad($value, $maxDigits, '0', STR_PAD_LEFT);
495
496	$line = $value . $line;
497
498	if ($j === 0) {
499	break;
500	}
501	}
502
503	if ($carry !== 0) {
504	$line = $carry . $line;
505	}
506
507	$line = \ltrim($line, '0');
508
509	if ($line !== '') {
510	$line .= \str_repeat('0', $x - $blockALength - $i);
511	$result = $this->add($result, $line);
512	}
513
514	if ($i === 0) {
515	break;
516	}
517	}
518
519	return $result;
520	}
521
522	/**
523	* Performs the division of two non-signed large integers.
524	*
525	* @param string $a The first operand.
526	* @param string $b The second operand.
527	*
528	* @return string[] The quotient and remainder.
529	*/
530	private function doDiv(string $a, string $b) : array
531	{
532	$cmp = $this->doCmp($a, $b);
533
534	if ($cmp === -1) {
535	return ['0', $a];
536	}
537
538	$x = \strlen($a);
539	$y = \strlen($b);
540
541	// we now know that a >= b && x >= y
542
543	$q = '0'; // quotient
544	$r = $a; // remainder
545	$z = $y; // focus length, always $y or $y+1
546
547	for (;;) {
548	$focus = \substr($a, 0, $z);
549
550	$cmp = $this->doCmp($focus, $b);
551
552	if ($cmp === -1) {
553	if ($z === $x) { // remainder < dividend
554	break;
555	}
556
557	$z++;
558	}
559
560	$zeros = \str_repeat('0', $x - $z);
561
562	$q = $this->add($q, '1' . $zeros);
563	$a = $this->sub($a, $b . $zeros);
564
565	$r = $a;
566
567	if ($r === '0') { // remainder == 0
568	break;
569	}
570
571	$x = \strlen($a);
572
573	if ($x < $y) { // remainder < dividend
574	break;
575	}
576
577	$z = $y;
578	}
579
580	return [$q, $r];
581	}
582
583	/**
584	* Compares two non-signed large numbers.
585	*
586	* @param string $a The first operand.
587	* @param string $b The second operand.
588	*
589	* @return int [-1, 0, 1]
590	*/
591	private function doCmp(string $a, string $b) : int
592	{
593	$x = \strlen($a);
594	$y = \strlen($b);
595
596	$cmp = $x <=> $y;
597
598	if ($cmp !== 0) {
599	return $cmp;
600	}
601
602	return \strcmp($a, $b) <=> 0; // enforce [-1, 0, 1]
603	}
604
605	/**
606	* Pads the left of one of the given numbers with zeros if necessary to make both numbers the same length.
607	*
608	* The numbers must only consist of digits, without leading minus sign.
609	*
610	* @param string $a The first operand.
611	* @param string $b The second operand.
612	*
613	* @return array{string, string, int}
614	*/
615	private function pad(string $a, string $b) : array
616	{
617	$x = \strlen($a);
618	$y = \strlen($b);
619
620	if ($x > $y) {
621	$b = \str_repeat('0', $x - $y) . $b;
622
623	return [$a, $b, $x];
624	}
625
626	if ($x < $y) {
627	$a = \str_repeat('0', $y - $x) . $a;
628
629	return [$a, $b, $y];
630	}
631
632	return [$a, $b, $x];
633	}
634	}
635