[Summary view] [Print] [Text view]

   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{0: bool, 1: bool, 2: string, 3: 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.
 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 = $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  }