media-cloud-sync / includes / sdk / google / brick / math / src / Internal / Calculator.php

Calculator.php in Media Cloud Sync 1.1.1, at includes/sdk/google/brick/math/src/Internal/Calculator.php

630 lines 20.1 KB

Raw Download Zip

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