defender-security / vendor / brick / math / src / Internal / Calculator.php

Calculator.php in Defender Security – Malware Scanner, Login Security & Firewall 6.3.0, at vendor/brick/math/src/Internal/Calculator.php

757 lines 20.5 KB

Raw Download Zip

1	<?php
2
3	declare(strict_types=1);
4
5	namespace Brick\Math\Internal;
6
7	use Brick\Math\Exception\RoundingNecessaryException;
8	use Brick\Math\RoundingMode;
9
10	/**
11	* Performs basic operations on arbitrary size integers.
12	*
13	* Unless otherwise specified, all parameters must be validated as non-empty strings of digits,
14	* without leading zero, and with an optional leading minus sign if the number is not zero.
15	*
16	* Any other parameter format will lead to undefined behaviour.
17	* All methods must return strings respecting this format, unless specified otherwise.
18	*
19	* @internal
20	*
21	* @psalm-immutable
22	*/
23	abstract class Calculator
24	{
25	/**
26	* The maximum exponent value allowed for the pow() method.
27	*/
28	public const MAX_POWER = 1000000;
29
30	/**
31	* The alphabet for converting from and to base 2 to 36, lowercase.
32	*/
33	public const ALPHABET = '0123456789abcdefghijklmnopqrstuvwxyz';
34
35	/**
36	* The Calculator instance in use.
37	*
38	* @var Calculator\|null
39	*/
40	private static $instance;
41
42	/**
43	* Sets the Calculator instance to use.
44	*
45	* An instance is typically set only in unit tests: the autodetect is usually the best option.
46	*
47	* @param Calculator\|null $calculator The calculator instance, or NULL to revert to autodetect.
48	*
49	* @return void
50	*/
51	final public static function set(?Calculator $calculator) : void
52	{
53	self::$instance = $calculator;
54	}
55
56	/**
57	* Returns the Calculator instance to use.
58	*
59	* If none has been explicitly set, the fastest available implementation will be returned.
60	*
61	* @return Calculator
62	*
63	* @psalm-pure
64	* @psalm-suppress ImpureStaticProperty
65	*/
66	final public static function get() : Calculator
67	{
68	if (self::$instance === null) {
69	/** @psalm-suppress ImpureMethodCall */
70	self::$instance = self::detect();
71	}
72
73	return self::$instance;
74	}
75
76	/**
77	* Returns the fastest available Calculator implementation.
78	*
79	* @codeCoverageIgnore
80	*
81	* @return Calculator
82	*/
83	private static function detect() : Calculator
84	{
85	if (\extension_loaded('gmp')) {
86	return new Calculator\GmpCalculator();
87	}
88
89	if (\extension_loaded('bcmath')) {
90	return new Calculator\BcMathCalculator();
91	}
92
93	return new Calculator\NativeCalculator();
94	}
95
96	/**
97	* Extracts the sign & digits of the operands.
98	*
99	* @param string $a The first operand.
100	* @param string $b The second operand.
101	*
102	* @return array{bool, bool, string, string} Whether $a and $b are negative, followed by their digits.
103	*/
104	final protected function init(string $a, string $b) : array
105	{
106	return [
107	$aNeg = ($a[0] === '-'),
108	$bNeg = ($b[0] === '-'),
109
110	$aNeg ? \substr($a, 1) : $a,
111	$bNeg ? \substr($b, 1) : $b,
112	];
113	}
114
115	/**
116	* Returns the absolute value of a number.
117	*
118	* @param string $n The number.
119	*
120	* @return string The absolute value.
121	*/
122	final public function abs(string $n) : string
123	{
124	return ($n[0] === '-') ? \substr($n, 1) : $n;
125	}
126
127	/**
128	* Negates a number.
129	*
130	* @param string $n The number.
131	*
132	* @return string The negated value.
133	*/
134	final public function neg(string $n) : string
135	{
136	if ($n === '0') {
137	return '0';
138	}
139
140	if ($n[0] === '-') {
141	return \substr($n, 1);
142	}
143
144	return '-' . $n;
145	}
146
147	/**
148	* Compares two numbers.
149	*
150	* @param string $a The first number.
151	* @param string $b The second number.
152	*
153	* @return int [-1, 0, 1] If the first number is less than, equal to, or greater than the second number.
154	*/
155	final public function cmp(string $a, string $b) : int
156	{
157	[$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b);
158
159	if ($aNeg && ! $bNeg) {
160	return -1;
161	}
162
163	if ($bNeg && ! $aNeg) {
164	return 1;
165	}
166
167	$aLen = \strlen($aDig);
168	$bLen = \strlen($bDig);
169
170	if ($aLen < $bLen) {
171	$result = -1;
172	} elseif ($aLen > $bLen) {
173	$result = 1;
174	} else {
175	$result = $aDig <=> $bDig;
176	}
177
178	return $aNeg ? -$result : $result;
179	}
180
181	/**
182	* Adds two numbers.
183	*
184	* @param string $a The augend.
185	* @param string $b The addend.
186	*
187	* @return string The sum.
188	*/
189	abstract public function add(string $a, string $b) : string;
190
191	/**
192	* Subtracts two numbers.
193	*
194	* @param string $a The minuend.
195	* @param string $b The subtrahend.
196	*
197	* @return string The difference.
198	*/
199	abstract public function sub(string $a, string $b) : string;
200
201	/**
202	* Multiplies two numbers.
203	*
204	* @param string $a The multiplicand.
205	* @param string $b The multiplier.
206	*
207	* @return string The product.
208	*/
209	abstract public function mul(string $a, string $b) : string;
210
211	/**
212	* Returns the quotient of the division of two numbers.
213	*
214	* @param string $a The dividend.
215	* @param string $b The divisor, must not be zero.
216	*
217	* @return string The quotient.
218	*/
219	abstract public function divQ(string $a, string $b) : string;
220
221	/**
222	* Returns the remainder of the division of two numbers.
223	*
224	* @param string $a The dividend.
225	* @param string $b The divisor, must not be zero.
226	*
227	* @return string The remainder.
228	*/
229	abstract public function divR(string $a, string $b) : string;
230
231	/**
232	* Returns the quotient and remainder of the division of two numbers.
233	*
234	* @param string $a The dividend.
235	* @param string $b The divisor, must not be zero.
236	*
237	* @return string[] An array containing the quotient and remainder.
238	*/
239	abstract public function divQR(string $a, string $b) : array;
240
241	/**
242	* Exponentiates a number.
243	*
244	* @param string $a The base number.
245	* @param int $e The exponent, validated as an integer between 0 and MAX_POWER.
246	*
247	* @return string The power.
248	*/
249	abstract public function pow(string $a, int $e) : string;
250
251	/**
252	* @param string $a
253	* @param string $b The modulus; must not be zero.
254	*
255	* @return string
256	*/
257	public function mod(string $a, string $b) : string
258	{
259	return $this->divR($this->add($this->divR($a, $b), $b), $b);
260	}
261
262	/**
263	* Returns the modular multiplicative inverse of $x modulo $m.
264	*
265	* If $x has no multiplicative inverse mod m, this method must return null.
266	*
267	* This method can be overridden by the concrete implementation if the underlying library has built-in support.
268	*
269	* @param string $x
270	* @param string $m The modulus; must not be negative or zero.
271	*
272	* @return string\|null
273	*/
274	public function modInverse(string $x, string $m) : ?string
275	{
276	if ($m === '1') {
277	return '0';
278	}
279
280	$modVal = $x;
281
282	if ($x[0] === '-' \|\| ($this->cmp($this->abs($x), $m) >= 0)) {
283	$modVal = $this->mod($x, $m);
284	}
285
286	$x = '0';
287	$y = '0';
288	$g = $this->gcdExtended($modVal, $m, $x, $y);
289
290	if ($g !== '1') {
291	return null;
292	}
293
294	return $this->mod($this->add($this->mod($x, $m), $m), $m);
295	}
296
297	/**
298	* Raises a number into power with modulo.
299	*
300	* @param string $base The base number; must be positive or zero.
301	* @param string $exp The exponent; must be positive or zero.
302	* @param string $mod The modulus; must be strictly positive.
303	*
304	* @return string The power.
305	*/
306	abstract public function modPow(string $base, string $exp, string $mod) : string;
307
308	/**
309	* Returns the greatest common divisor of the two numbers.
310	*
311	* This method can be overridden by the concrete implementation if the underlying library
312	* has built-in support for GCD calculations.
313	*
314	* @param string $a The first number.
315	* @param string $b The second number.
316	*
317	* @return string The GCD, always positive, or zero if both arguments are zero.
318	*/
319	public function gcd(string $a, string $b) : string
320	{
321	if ($a === '0') {
322	return $this->abs($b);
323	}
324
325	if ($b === '0') {
326	return $this->abs($a);
327	}
328
329	return $this->gcd($b, $this->divR($a, $b));
330	}
331
332	private function gcdExtended(string $a, string $b, string &$x, string &$y) : string
333	{
334	if ($a === '0') {
335	$x = '0';
336	$y = '1';
337
338	return $b;
339	}
340
341	$x1 = '0';
342	$y1 = '0';
343
344	$gcd = $this->gcdExtended($this->mod($b, $a), $a, $x1, $y1);
345
346	$x = $this->sub($y1, $this->mul($this->divQ($b, $a), $x1));
347	$y = $x1;
348
349	return $gcd;
350	}
351
352	/**
353	* Returns the square root of the given number, rounded down.
354	*
355	* The result is the largest x such that x² ≤ n.
356	* The input MUST NOT be negative.
357	*
358	* @param string $n The number.
359	*
360	* @return string The square root.
361	*/
362	abstract public function sqrt(string $n) : string;
363
364	/**
365	* Converts a number from an arbitrary base.
366	*
367	* This method can be overridden by the concrete implementation if the underlying library
368	* has built-in support for base conversion.
369	*
370	* @param string $number The number, positive or zero, non-empty, case-insensitively validated for the given base.
371	* @param int $base The base of the number, validated from 2 to 36.
372	*
373	* @return string The converted number, following the Calculator conventions.
374	*/
375	public function fromBase(string $number, int $base) : string
376	{
377	return $this->fromArbitraryBase(\strtolower($number), self::ALPHABET, $base);
378	}
379
380	/**
381	* Converts a number to an arbitrary base.
382	*
383	* This method can be overridden by the concrete implementation if the underlying library
384	* has built-in support for base conversion.
385	*
386	* @param string $number The number to convert, following the Calculator conventions.
387	* @param int $base The base to convert to, validated from 2 to 36.
388	*
389	* @return string The converted number, lowercase.
390	*/
391	public function toBase(string $number, int $base) : string
392	{
393	$negative = ($number[0] === '-');
394
395	if ($negative) {
396	$number = \substr($number, 1);
397	}
398
399	$number = $this->toArbitraryBase($number, self::ALPHABET, $base);
400
401	if ($negative) {
402	return '-' . $number;
403	}
404
405	return $number;
406	}
407
408	/**
409	* Converts a non-negative number in an arbitrary base using a custom alphabet, to base 10.
410	*
411	* @param string $number The number to convert, validated as a non-empty string,
412	* containing only chars in the given alphabet/base.
413	* @param string $alphabet The alphabet that contains every digit, validated as 2 chars minimum.
414	* @param int $base The base of the number, validated from 2 to alphabet length.
415	*
416	* @return string The number in base 10, following the Calculator conventions.
417	*/
418	final public function fromArbitraryBase(string $number, string $alphabet, int $base) : string
419	{
420	// remove leading "zeros"
421	$number = \ltrim($number, $alphabet[0]);
422
423	if ($number === '') {
424	return '0';
425	}
426
427	// optimize for "one"
428	if ($number === $alphabet[1]) {
429	return '1';
430	}
431
432	$result = '0';
433	$power = '1';
434
435	$base = (string) $base;
436
437	for ($i = \strlen($number) - 1; $i >= 0; $i--) {
438	$index = \strpos($alphabet, $number[$i]);
439
440	if ($index !== 0) {
441	$result = $this->add($result, ($index === 1)
442	? $power
443	: $this->mul($power, (string) $index)
444	);
445	}
446
447	if ($i !== 0) {
448	$power = $this->mul($power, $base);
449	}
450	}
451
452	return $result;
453	}
454
455	/**
456	* Converts a non-negative number to an arbitrary base using a custom alphabet.
457	*
458	* @param string $number The number to convert, positive or zero, following the Calculator conventions.
459	* @param string $alphabet The alphabet that contains every digit, validated as 2 chars minimum.
460	* @param int $base The base to convert to, validated from 2 to alphabet length.
461	*
462	* @return string The converted number in the given alphabet.
463	*/
464	final public function toArbitraryBase(string $number, string $alphabet, int $base) : string
465	{
466	if ($number === '0') {
467	return $alphabet[0];
468	}
469
470	$base = (string) $base;
471	$result = '';
472
473	while ($number !== '0') {
474	[$number, $remainder] = $this->divQR($number, $base);
475	$remainder = (int) $remainder;
476
477	$result .= $alphabet[$remainder];
478	}
479
480	return \strrev($result);
481	}
482
483	/**
484	* Performs a rounded division.
485	*
486	* Rounding is performed when the remainder of the division is not zero.
487	*
488	* @param string $a The dividend.
489	* @param string $b The divisor, must not be zero.
490	* @param int $roundingMode The rounding mode.
491	*
492	* @return string
493	*
494	* @throws \InvalidArgumentException If the rounding mode is invalid.
495	* @throws RoundingNecessaryException If RoundingMode::UNNECESSARY is provided but rounding is necessary.
496	*/
497	final public function divRound(string $a, string $b, int $roundingMode) : string
498	{
499	[$quotient, $remainder] = $this->divQR($a, $b);
500
501	$hasDiscardedFraction = ($remainder !== '0');
502	$isPositiveOrZero = ($a[0] === '-') === ($b[0] === '-');
503
504	$discardedFractionSign = function() use ($remainder, $b) : int {
505	$r = $this->abs($this->mul($remainder, '2'));
506	$b = $this->abs($b);
507
508	return $this->cmp($r, $b);
509	};
510
511	$increment = false;
512
513	switch ($roundingMode) {
514	case RoundingMode::UNNECESSARY:
515	if ($hasDiscardedFraction) {
516	throw RoundingNecessaryException::roundingNecessary();
517	}
518	break;
519
520	case RoundingMode::UP:
521	$increment = $hasDiscardedFraction;
522	break;
523
524	case RoundingMode::DOWN:
525	break;
526
527	case RoundingMode::CEILING:
528	$increment = $hasDiscardedFraction && $isPositiveOrZero;
529	break;
530
531	case RoundingMode::FLOOR:
532	$increment = $hasDiscardedFraction && ! $isPositiveOrZero;
533	break;
534
535	case RoundingMode::HALF_UP:
536	$increment = $discardedFractionSign() >= 0;
537	break;
538
539	case RoundingMode::HALF_DOWN:
540	$increment = $discardedFractionSign() > 0;
541	break;
542
543	case RoundingMode::HALF_CEILING:
544	$increment = $isPositiveOrZero ? $discardedFractionSign() >= 0 : $discardedFractionSign() > 0;
545	break;
546
547	case RoundingMode::HALF_FLOOR:
548	$increment = $isPositiveOrZero ? $discardedFractionSign() > 0 : $discardedFractionSign() >= 0;
549	break;
550
551	case RoundingMode::HALF_EVEN:
552	$lastDigit = (int) $quotient[-1];
553	$lastDigitIsEven = ($lastDigit % 2 === 0);
554	$increment = $lastDigitIsEven ? $discardedFractionSign() > 0 : $discardedFractionSign() >= 0;
555	break;
556
557	default:
558	throw new \InvalidArgumentException('Invalid rounding mode.');
559	}
560
561	if ($increment) {
562	return $this->add($quotient, $isPositiveOrZero ? '1' : '-1');
563	}
564
565	return $quotient;
566	}
567
568	/**
569	* Calculates bitwise AND of two numbers.
570	*
571	* This method can be overridden by the concrete implementation if the underlying library
572	* has built-in support for bitwise operations.
573	*
574	* @param string $a
575	* @param string $b
576	*
577	* @return string
578	*/
579	public function and(string $a, string $b) : string
580	{
581	return $this->bitwise('and', $a, $b);
582	}
583
584	/**
585	* Calculates bitwise OR of two numbers.
586	*
587	* This method can be overridden by the concrete implementation if the underlying library
588	* has built-in support for bitwise operations.
589	*
590	* @param string $a
591	* @param string $b
592	*
593	* @return string
594	*/
595	public function or(string $a, string $b) : string
596	{
597	return $this->bitwise('or', $a, $b);
598	}
599
600	/**
601	* Calculates bitwise XOR of two numbers.
602	*
603	* This method can be overridden by the concrete implementation if the underlying library
604	* has built-in support for bitwise operations.
605	*
606	* @param string $a
607	* @param string $b
608	*
609	* @return string
610	*/
611	public function xor(string $a, string $b) : string
612	{
613	return $this->bitwise('xor', $a, $b);
614	}
615
616	/**
617	* Performs a bitwise operation on a decimal number.
618	*
619	* @param string $operator The operator to use, must be "and", "or" or "xor".
620	* @param string $a The left operand.
621	* @param string $b The right operand.
622	*
623	* @return string
624	*/
625	private function bitwise(string $operator, string $a, string $b) : string
626	{
627	[$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b);
628
629	$aBin = $this->toBinary($aDig);
630	$bBin = $this->toBinary($bDig);
631
632	$aLen = \strlen($aBin);
633	$bLen = \strlen($bBin);
634
635	if ($aLen > $bLen) {
636	$bBin = \str_repeat("\x00", $aLen - $bLen) . $bBin;
637	} elseif ($bLen > $aLen) {
638	$aBin = \str_repeat("\x00", $bLen - $aLen) . $aBin;
639	}
640
641	if ($aNeg) {
642	$aBin = $this->twosComplement($aBin);
643	}
644	if ($bNeg) {
645	$bBin = $this->twosComplement($bBin);
646	}
647
648	switch ($operator) {
649	case 'and':
650	$value = $aBin & $bBin;
651	$negative = ($aNeg and $bNeg);
652	break;
653
654	case 'or':
655	$value = $aBin \| $bBin;
656	$negative = ($aNeg or $bNeg);
657	break;
658
659	case 'xor':
660	$value = $aBin ^ $bBin;
661	$negative = ($aNeg xor $bNeg);
662	break;
663
664	// @codeCoverageIgnoreStart
665	default:
666	throw new \InvalidArgumentException('Invalid bitwise operator.');
667	// @codeCoverageIgnoreEnd
668	}
669
670	if ($negative) {
671	$value = $this->twosComplement($value);
672	}
673
674	$result = $this->toDecimal($value);
675
676	return $negative ? $this->neg($result) : $result;
677	}
678
679	/**
680	* @param string $number A positive, binary number.
681	*
682	* @return string
683	*/
684	private function twosComplement(string $number) : string
685	{
686	$xor = \str_repeat("\xff", \strlen($number));
687
688	$number ^= $xor;
689
690	for ($i = \strlen($number) - 1; $i >= 0; $i--) {
691	$byte = \ord($number[$i]);
692
693	if (++$byte !== 256) {
694	$number[$i] = \chr($byte);
695	break;
696	}
697
698	$number[$i] = "\x00";
699
700	if ($i === 0) {
701	$number = "\x01" . $number;
702	}
703	}
704
705	return $number;
706	}
707
708	/**
709	* Converts a decimal number to a binary string.
710	*
711	* @param string $number The number to convert, positive or zero, only digits.
712	*
713	* @return string
714	*/
715	private function toBinary(string $number) : string
716	{
717	$result = '';
718
719	while ($number !== '0') {
720	[$number, $remainder] = $this->divQR($number, '256');
721	$result .= \chr((int) $remainder);
722	}
723
724	return \strrev($result);
725	}
726
727	/**
728	* Returns the positive decimal representation of a binary number.
729	*
730	* @param string $bytes The bytes representing the number.
731	*
732	* @return string
733	*/
734	private function toDecimal(string $bytes) : string
735	{
736	$result = '0';
737	$power = '1';
738
739	for ($i = \strlen($bytes) - 1; $i >= 0; $i--) {
740	$index = \ord($bytes[$i]);
741
742	if ($index !== 0) {
743	$result = $this->add($result, ($index === 1)
744	? $power
745	: $this->mul($power, (string) $index)
746	);
747	}
748
749	if ($i !== 0) {
750	$power = $this->mul($power, '256');
751	}
752	}
753
754	return $result;
755	}
756	}
757