source: trunk/Packages/Common/BigInt.php

<?php

define('INT64', 64);
define('INT128', 128);
define('INT256', 256);
define('INT512', 512);

// BigInt represented as string of characters
// First byte is MSB and last byte is LSB

function BigIntNew($BitWidth): string
{
  return str_repeat(chr(0), $BitWidth >> 3);
}

function BigIntNewAs($A): string
{
  return str_repeat(chr(0), strlen($A));
}

function BigIntCheck(string $A, string $B): void
{
    if (strlen($A) != strlen($B))
      throw new Exception('BigInt parameters bit width doesn\'t match.');
}

function BigIntAdd(string $A, string $B): string
{
  BigIntCheck($A, $B);
  $Result = BigIntNewAs($A);
  $Carry = 0;
  for ($I = strlen($Result) - 1; $I >= 0; $I--)
  {
    $Sum = ord($A[$I]) + ord($B[$I]) + $Carry;
    $Result[$I] = chr($Sum);
    if ($Sum > 255) $Carry = 1;
      else $Carry = 0;
  }
  return $Result;
}

function BigIntSub(string $A, string $B): string
{
  BigIntCheck($A, $B);
  $Result = BigIntNewAs($A);
  $Carry = 0;
  for ($I = strlen($Result) - 1; $I >= 0; $I--)
  {
    $Sum = ord($A[$I]) - ord($B[$I]) - $Carry;
    $Result[$I] = chr($Sum);
    if ($Sum < 0) $Carry = 1;
      else $Carry = 0;
  }
  return $Result;
}

function BigIntInc(string $A): string
{
  $Result = BigIntNewAs($A);
  $Carry = 1;
  for ($I = strlen($Result) - 1; $I >= 0; $I--)
  {
    $Sum = ord($A[$I]) + $Carry;
    $Result[$I] = chr($Sum);
    if ($Sum > 255) $Carry = 1;
      else $Carry = 0;
  }
  return $Result;
}

function BigIntDec(string $A): string
{
  $Result = BigIntNewAs($A);
  $Carry = 1;
  for ($I = strlen($Result) - 1; $I >= 0; $I--)
  {
    $Sum = ord($A[$I]) - $Carry;
    $Result[$I] = chr($Sum);
    if ($Sum < 0) $Carry = 1;
      else $Carry = 0;
  }
  return $Result;
}

function BigIntNeg(string $A): string
{
  return BigIntInc(BigIntNot($A));
}

function BigIntIsNeg(string $A): string
{
  return ord($A[0]) & 0x80;
}

function BigIntEqual(string $A, string $B): bool
{
  return $A == $B; // Simple string comparison
}

function BigIntNotEqual(string $A, string $B): bool
{
  return $A != $B; // Simple string comparison
}

function BigIntGreater(string $A, string $B): bool
{
  return BigIntIsNeg(BigIntSub($B, $A));
}

function BigIntGreaterOrEqual(string $A, string $B): bool
{
  return BigIntIsNeg(BigIntSub($B, $A)) or BigIntEqual($A, $B);
}

function BigIntLesser(string $A, string $B): bool
{
  return BigIntIsNeg(BigIntSub($A, $B));
}

function BigIntLesserOrEqual(string $A, string $B): bool
{
  return BigIntIsNeg(BigIntSub($A, $B)) or BigIntEqual($A, $B);
}

function BigIntMul(string $A, string $B): string
{
  BigIntCheck($A, $B);
  $Result = BigIntNewAs($A);
  while (BigIntGreater($B, BigIntNewAs($A)))
  {
    $Result = BigIntAdd($Result, $A);
    $B = BigIntDec($B);
  }
  return $Result;
}

function BigIntDiv(string $A, string $B): string
{
  BigIntCheck($A, $B);
  $Result = BigIntNewAs($A);
  while (BigIntGreaterOrEqual($A, $B))
  {
    $A = BigIntSub($A, $B);
    $Result = BigIntInc($Result);
  }
  return $Result;
}

function BigIntMod(string $A, string $B): string
{
  BigIntCheck($A, $B);
  $Result = BigIntNewAs($A);
  while (BigIntGreaterOrEqual($A, $B))
  {
    $A = BigIntSub($A, $B);
    $Result = BigIntInc($Result);
  }
  return $A;
}

function BigIntAnd(string $A, string $B): string
{
  BigIntCheck($A, $B);
  $Result = BigIntNewAs($A);
  for ($I = 0; $I < strlen($Result); $I++)
  {
    $Result[$I] = chr(ord($A[$I]) & ord($B[$I]));
  }
  return $Result;
}

function BigIntOr(string $A, string $B): string
{
  BigIntCheck($A, $B);
  $Result = BigIntNewAs($A);
  for ($I = 0; $I < strlen($Result); $I++)
  {
    $Result[$I] = chr(ord($A[$I]) | ord($B[$I]));
  }
  return $Result;
}

function BigIntXor(string $A, string $B): string
{
  BigIntCheck($A, $B);
  $Result = BigIntNewAs($A);
  for ($I = 0; $I < strlen($Result); $I++)
  {
    $Result[$I] = chr(ord($A[$I]) ^ ord($B[$I]));
  }
  return $Result;
}

function BigIntNot(string $A): string
{
  $Result = BigIntNewAs($A);
  for ($I = 0; $I < strlen($Result); $I++)
  {
    $Result[$I] = chr(~ord($A[$I]));
  }
  return $Result;
}

function BigIntShl1(string $A): string
{
  $Result = BigIntNewAs($A);
  for ($I = 0; $I < strlen($Result) - 1; $I++)
  {
    $Result[$I] = chr((ord($A[$I]) << 1) | (ord($A[$I + 1]) >> 7));
  }
  $Result[strlen($Result) - 1] = chr(ord($A[strlen($Result) - 1]) << 1);
  return $Result;
}

function BigIntShl(string $A, string $B): string
{
  BigIntCheck($A, $B);
  $Result = $A;
  for ($I = 0; $I < Int128ToInt($B); $I++)
  {
    $Result = BigIntShl1($Result);
  }
  return $Result;
}

function BigIntShr1(string $A): string
{
  $Result = BigIntNewAs($A);
  for ($I = strlen($Result) - 1; $I > 0; $I--)
  {
    $Result[$I] = chr((ord($A[$I]) >> 1) | ((ord($A[$I - 1]) & 1) << 7));
  }
  $Result[0] = chr(ord($A[0]) >> 1);
  return $Result;
}

function BigIntShr(string $A, string $B): string
{
  BigIntCheck($A, $B);
  $Result = $A;
  for ($I = 0; $I < Int128ToInt($B); $I++)
  {
    $Result = BigIntShr1($Result);
  }
  return $Result;
}

function BigIntToHex(string $A): string
{
  $Result = '';
  for ($I = 0; $I < strlen($A); $I++)
  {
    $Result .= str_pad(dechex(ord($A[$I])), 2, '0', STR_PAD_LEFT);
  }
  return $Result;
}

function HexToBigInt(string $A, int $BitWidth): string
{
  $Result = BigIntNew($BitWidth);
  $I = strlen($A) - 1;
  $Index = 15;
  while (($I >= 0) && ($Index >= 0))
  {
    $Result[$Index] = chr(ord($Result[$Index]) | hexdec($A[$I]));
    $I--;
    if ($I >= 0)
    {
      $Result[$Index] = chr(ord($Result[$Index]) | (hexdec($A[$I]) << 4));
      $I--;
    }
    $Index--;
  }
  return $Result;
}

function BigIntToBin(string $A): string
{
  $Result = '';
  for ($I = 0; $I < strlen($A); $I++)
  {
    $Result .= str_pad(decbin(ord($A[$I])), 8, '0', STR_PAD_LEFT);
  }
  return $Result;
}

function BinToBigInt(string $A, int $BitWidth): string
{
  $Result = BigIntNew($BitWidth);
  $I = strlen($A) - 1;
  $Index = strlen($Result) - 1;
  while (($I >= 0) && ($Index >= 0))
  {
    for ($J = 0; $J < 7; $J++)
    {
      if ($I >= 0)
      {
        $Result[$Index] = chr(ord($Result[$Index]) | (bindec($A[$I]) << $J));
        $I--;
      }
    }
    $Index--;
  }
  return $Result;
}

function BigIntToInt(string $A): int
{
  // 32-bit int support
  return ord($A[15]) | (ord($A[14]) << 8) | (ord($A[13]) << 16) | (ord($A[12]) << 24);
}

function IntToBigInt(int $A, int $BitWidth): string
{
  $Result = BigIntNew($BitWidth);
  // 32-bit int support
  $Result[15] = chr($A & 0xff);
  $Result[14] = chr(($A >> 8) & 0xff);
  $Result[13] = chr(($A >> 16) & 0xff);
  $Result[12] = chr(($A >> 24) & 0xff);
  return $Result;
}

function BigIntToDec(string $A): string
{
  $BitWidth = strlen($A) << 3;
  $Result = '';
  $Zero = BigIntNewAs($A);
  while (BigIntGreater($A, $Zero))
  {
    $Result = strval(BigIntToInt(BigIntMod($A, IntToBigInt(10, $BitWidth)))).$Result;
    $A = BigIntDiv($A, IntToBigInt(10, $BitWidth));
  }
  return $Result;
}

function DecToBigInt(string $A, int $BitWidth): string
{
  $Result = BigIntNew($BitWidth);
  $I = 0;
  while ($I < strlen($A))
  {
    $Result = BigIntMul($Result, IntToBigInt(10, $BitWidth));
    $Result = BigIntAdd($Result, IntToBigInt(intval($A[$I]), $BitWidth));
    $I++;
  }
  return $Result;
}