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

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

547 lines 18.4 KB

Raw Download Zip

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