long.php

<?php

/*
 * This file is part of php-restcord.
 *
 * (c) Aaron Scherer <[email protected]>
 *
 * This source file is subject to the license that is bundled
 * with this source code in the file LICENSE
 */

namespace RestCord\Type;

/**
 * @author Aaron Scherer <[email protected]>
 *
 * Long Class
 *
 * PHP Implementation of: https://github.com/mongodb/js-bson/blob/1.0-branch/lib/bson/long.js
 */
class Long
{
    /**
     * A cache of the Long representations of small integer values.
     * @type {Object}
     *
     * @ignore
     */
    private static $INT_CACHE = [];

    /**
     * Number used repeated below in calculations.  This must appear before the
     * first call to any from* function below.
     * @type {number}
     *
     * @ignore
     */
    const TWO_PWR_16_DBL = 1 << 16;

    /**
     * @type {number}
     * @ignore
     */
    const TWO_PWR_24_DBL = 1 << 24;

    /**
     * @type {number}
     * @ignore
     */
    const TWO_PWR_32_DBL = Long::TWO_PWR_16_DBL * Long::TWO_PWR_16_DBL;

    /**
     * @type {number}
     * @ignore
     */
    const TWO_PWR_31_DBL = Long::TWO_PWR_32_DBL / 2;

    /**
     * @type {number}
     * @ignore
     */
    const TWO_PWR_48_DBL = Long::TWO_PWR_32_DBL * Long::TWO_PWR_16_DBL;

    /**
     * @type {number}
     * @ignore
     */
    const TWO_PWR_64_DBL = Long::TWO_PWR_32_DBL * Long::TWO_PWR_32_DBL;

    /**
     * @type {number}
     * @ignore
     */
    const TWO_PWR_63_DBL = Long::TWO_PWR_64_DBL / 2;

    public static function ZERO()
    {
        return Long::fromInt32(0);
    }

    public static function ONE()
    {
        return Long::fromInt32(1);
    }

    public static function NEG_ONE()
    {
        return Long::fromInt32(-1);
    }

    public static function MIN_VALUE()
    {
        return Long::fromBits(0, 0x80000000 | 0);
    }

    public static function MAX_VALUE()
    {
        return Long::fromBits(0xFFFFFFFF | 0, 0x7FFFFFFF | 0);
    }

    public static function TWO_PWR_24()
    {
        return Long::fromInt32(1 << 24);
    }

    /**
     * Returns a Long representing the given (32-bit) integer value.
     *
     * @param int $value the 32-bit integer in question.
     *
     * @return Long the corresponding Long value.
     */
    public static function fromInt32($value)
    {
        if (-128 <= $value && $value < 128) {
            if (isset(static::$INT_CACHE[$value])) {
                return static::$INT_CACHE[$value];
            }
        }

        $obj = new static($value | 0, $value < 0 ? -1 : 0);
        if (-128 <= $value && $value < 128) {
            static::$INT_CACHE[$value] = $obj;
        }

        return $obj;
    }

    /**
     * Returns a Long representing the given value, provided that it is a finite number. Otherwise, zero is returned.
     *
     * @param int $value the number in question.
     *
     * @return Long the corresponding Long value.
     */
    public static function fromInt64($value)
    {
        if (is_nan($value)) {
            return static::ZERO();
        } elseif ($value <= -static::TWO_PWR_63_DBL) {
            return static::MIN_VALUE();
        } elseif ($value + 1 >= static::TWO_PWR_63_DBL) {
            return static::MAX_VALUE();
        } elseif ($value < 0) {
            return static::fromInt64(-$value)->negate();
        } else {
            return new static($value % static::TWO_PWR_32_DBL | 0, $value / static::TWO_PWR_32_DBL | 0);
        }
    }

    /**
     * Returns a Long representing the 64-bit integer that comes by concatenating the given high and low bits.
     * Each is assumed to use 32 bits.
     *
     * @param int $lowBits  the low 32-bits.
     * @param int $highBits the high 32-bits.
     *
     * @return Long the corresponding Long value.
     */
    public static function fromBits($lowBits, $highBits)
    {
        return new static($lowBits, $highBits);
    }

    /**
     * Returns a Long representation of the given string, written using the given radix.
     *
     * @param string $str   the textual representation of the Long.
     * @param int    $radix the radix in which the text is written.
     *
     * @return Long the corresponding Long value.
     * @throws \Exception
     */
    public static function fromString($str, $radix = 10)
    {
        if (strlen($str) === 0) {
            throw new \Exception('number format error: empty string');
        }

        if ($radix < 2 || 36 < $radix) {
            throw new \Exception('radix out of range: '.$radix);
        }

        if ($str[0] === '-') {
            return static::fromString(substr($str, 1), $radix)->negate();
        } elseif (strpos($str, '-') > 0) {
            throw new \Exception('number format error: interior "-" character: '.$str);
        }

        $radixToPower = static::fromInt64(pow($radix, 8));
        $result       = static::ZERO();
        for ($i = 0; $i < strlen($str); $i += 8) {
            $size  = min(8, strlen($str) - $i);
            $value = intval(substr($str, $i, $i + $size), $radix);
            $add   = static::fromInt64($value);
            if ($size < 8) {
                $power  = static::fromInt64(pow($radix, $size));
                $result = $result->multiply($power)->add($add);
            } else {
                $result = $result->multiply($radixToPower);
                $result = $result->add($add);
            }
        }

        return $result;
    }

    /**
     * @var integer
     */
    public $low;

    /**
     * @var integer
     */
    public $high;

    /**
     * Long constructor.
     * Defines a Long class for representing a 64-bit two's-complement
     * integer value, which faithfully simulates the behavior of a Java "Long". This
     * implementation is derived from LongLib in GWT.
     *
     * Constructs a 64-bit two's-complement integer, given its low and high 32-bit
     * values as *signed* integers.  See the from* functions below for more
     * convenient ways of constructing Longs.
     *
     * The internal representation of a Long is the two given signed, 32-bit values.
     * We use 32-bit pieces because these are the size of integers on which
     * Javascript performs bit-operations.  For operations like addition and
     * multiplication, we split each number into 16-bit pieces, which can easily be
     * multiplied within Javascript's floating-point representation without overflow
     * or change in sign.
     *
     * In the algorithms below, we frequently reduce the negative case to the
     * positive case by negating the input(s) and then post-processing the result.
     * Note that we must ALWAYS check specially whether those values are MIN_VALUE
     * (-2^63) because -MIN_VALUE == MIN_VALUE (since 2^63 cannot be represented as
     * a positive number, it overflows back into a negative).  Not handling this
     * case would often result in infinite recursion.
     *
     * @class
     *
     * @param int $low  The low (signed) 32 bits of the Long.
     * @param int $high The high (signed) 32 bits of the Long.
     *
     * @return Long
     */
    public function __construct($low, $high = null)
    {
        if ($high === null) {
            $long = static::fromString($low, 10);
            $low  = $long->low;
            $high = $long->high;
        }

        $this->low  = $low | 0;
        $this->high = $high | 0;
    }

    /**
     * Return the int value.
     *
     * @return integer The value, assuming it is a 32-bit integer.
     */
    public function toInt32()
    {
        return $this->low;
    }

    /**
     * Return the Number value.
     *
     * @return integer the closest floating-point representation to this value.
     */
    public function toInt64()
    {
        return $this->high * Long::TWO_PWR_32_DBL + $this->getLowBitsUnsigned();
    }

    /**
     * Return the JSON value.
     *
     * @method
     * @return string the JSON representation.
     */
    public function toJSON()
    {
        return $this->toString();
    }

    /**
     * Return the String value.
     *
     * @return string the textual representation of this value.
     * @throws \Exception
     */
    public function __toString()
    {
        return $this->toString();
    }

    /**
     * Return the String value.
     *
     * @param int $radix the radix in which the text should be written.
     *
     * @return string the textual representation of this value.
     * @throws \Exception
     */
    public function toString($radix = 10)
    {
        if ($radix < 2 || 36 < $radix) {
            throw new \Exception('radix out of range: '.$radix);
        }

        if ($this->isZero()) {
            return '0';
        }

        if ($this->isNegative()) {
            if ($this->equals(Long::MIN_VALUE())) {
                // We need to change the Long value before it can be negated, so we remove
                // the bottom-most digit in this base and then recurse to do the rest.
                $radixLong = static::fromInt64($radix);
                $div       = $this->divide($radixLong);
                $rem       = $div->multiply($radixLong)->subtract($this);

                return $div->toString().$rem->toInt32();
            } else {
                return '-' . $this->negate()->toString($radix);
            }
        }

        // Do several (6) digits each time through the loop, so as to
        // minimize the calls to the very expensive emulated div.
        $radixToPower = static::fromInt64(pow($radix, 6));

        $rem    = $this;
        $result = '';
        while (true) {
            $remDiv = $rem->divide($radixToPower);
            dump($remDiv);
            $digits = $rem->subtract($remDiv->multiply($radixToPower))->toInt32();
            dump([$remDiv, $digits]);

            if ($remDiv->isZero()) {
                return $digits . $result;
            } else {
                while (strlen((string) $digits) < 6) {
                    $digits = '0' . $digits;
                }
                $result = '' . $digits . $result;
            }
        }
    }

    /**
     * Return the high 32-bits value.
     *
     * @return int the high 32-bits as a signed value.
     */
    public function getHighBits()
    {
        return $this->high;
    }

    /**
     * Return the low 32-bits value.
     *
     * @return int the low 32-bits as a signed value.
     */
    public function getLowBits()
    {
        return $this->low;
    }

    /**
     * Return the low unsigned 32-bits value.
     *
     * @return int the low 32-bits as an unsigned value.
     */
    public function getLowBitsUnsigned()
    {
        return ($this->low >= 0) ?
            $this->low : static::TWO_PWR_32_DBL + $this->low;
    }

    /**
     * Returns the number of bits needed to represent the absolute value of this Long.
     *
     * @return int Returns the number of bits needed to represent the absolute value of this Long.
     */
    public function getNumBitsAbs()
    {
        if ($this->isNegative()) {
            if ($this->equals(static::MIN_VALUE())) {
                return 64;
            } else {
                return $this->negate()->getNumBitsAbs();
            }
        } else {
            $val = $this->high != 0 ? $this->high : $this->low;
            for ($bit = 31; $bit > 0; $bit--) {
                if (($val & (1 << $bit)) != 0) {
                    break;
                }
            }

            return $this->high != 0 ? $bit + 33 : $bit + 1;
        }
    }

    /**
     * Return whether this value is zero.
     *
     * @return boolean whether this value is zero.
     */
    public function isZero()
    {
        return $this->low === 0 && $this->high === 0;
    }

    /**
     * Return whether this value is negative.
     *
     * @method
     * @return boolean whether this value is negative.
     */
    public function isNegative()
    {
        return $this->high < 0;
    }

    /**
     * Return whether this value is odd.
     *
     * @method
     * @return boolean whether this value is odd.
     */
    public function isOdd()
    {
        return $this->low & 1 === 1;
    }

    /**
     * Return whether this Long equals the other
     *
     * @param Long $long Long to compare against.
     *
     * @return boolean whether this Long equals the other
     */
    public function equals(Long $long)
    {
        return $this->high === $long->high && $this->low === $long->low;
    }

    /**
     * Return whether this Long does not equal the $long->
     *
     * @param Long $long Long to compare against.
     *
     * @return boolean whether this Long does not equal the $long->
     */
    public function notEquals(Long $long)
    {
        return $this->high !== $long->high || $this->low !== $long->low;
    }

    /**
     * Return whether this Long is less than the $long->
     *
     * @param Long $long Long to compare against.
     *
     * @return boolean whether this Long is less than the $long->
     */
    public function lessThan(Long $long)
    {
        return $this->compare($long) < 0;
    }

    /**
     * Return whether this Long is less than or equal to the $long->
     *
     * @param Long $long Long to compare against.
     *
     * @return boolean whether this Long is less than or equal to the $long->
     */
    public function lessThanOrEqual(Long $long)
    {
        return $this->compare($long) <= 0;
    }

    /**
     * Return whether this Long is greater than the $long->
     *
     * @param Long $long Long to compare against.
     *
     * @return boolean whether this Long is greater than the $long->
     */
    public function greaterThan(Long $long)
    {
        return $this->compare($long) > 0;
    }

    /**
     * Return whether this Long is greater than or equal to the $long->
     *
     * @param Long $long Long to compare against.
     *
     * @return boolean whether this Long is greater than or equal to the $long->
     */
    public function greaterThanOrEqual(Long $long)
    {
        return $this->compare($long) >= 0;
    }

    /**
     * Compares this Long with the given one.
     *
     * @param Long $long Long to compare against.
     *
     * @return boolean 0 if they are the same, 1 if the this is greater, and -1 if the given one is greater.
     */
    public function compare(Long $long)
    {
        if ($this->equals($long)) {
            return 0;
        }

        $thisNeg  = $this->isNegative();
        $otherNeg = $long->isNegative();

        if ($thisNeg && !$otherNeg) {
            return -1;
        }
        if (!$thisNeg && $otherNeg) {
            return 1;
        }

        // at this point, the signs are the same, so subtraction will not overflow
        if ($this->subtract($long)->isNegative()) {
            return -1;
        } else {
            return 1;
        }
    }

    /**The negation of this value.
     *
     * @return Long the negation of this value.
     */
    public function negate()
    {
        return $this->equals(static::MIN_VALUE()) ? static::MIN_VALUE() : $this->not()->add(static::ONE());
    }

    /**
     * Returns the sum of this and the given Long.
     *
     * @param Long $long Long to add to this one.
     *
     * @return Long the sum of this and the given Long.
     */
    public function add(Long $long)
    {
        // Divide each number into 4 chunks of 16 bits, and then sum the chunks.

        $a48 = $this->zeroFill($this->high, 16);
        $a32 = $this->high & 0xFFFF;
        $a16 = $this->zeroFill($this->low, 16);
        $a00 = $this->low & 0xFFFF;

        $b48 = $this->zeroFill($long->high, 16);
        $b32 = $long->high & 0xFFFF;
        $b16 = $this->zeroFill($long->low, 16);
        $b00 = $long->low & 0xFFFF;

        $c48 = 0;
        $c32 = 0;
        $c16 = 0;
        $c00 = 0;

        $c00 += $a00 + $b00;
        $c16 += $this->zeroFill($c00, 16);
        $c00 &= 0xFFFF;
        $c16 += $a16 + $b16;
        $c32 += $this->zeroFill($c16, 16);
        $c16 &= 0xFFFF;
        $c32 += $a32 + $b32;
        $c48 += $this->zeroFill($c32, 16);
        $c32 &= 0xFFFF;
        $c48 += $a48 + $b48;
        $c48 &= 0xFFFF;

        return static::fromBits(($c16 << 16) | $c00, ($c48 << 16) | $c32);
    }

    /**
     * Returns the difference of this and the given Long.
     *
     * @param Long $long Long to subtract from $this->
     *
     * @return Long the difference of this and the given Long.
     */
    public function subtract(Long $long)
    {
        return $this->add($long->negate());
    }

    /**
     * Returns the product of this and the given Long.
     *
     * @method
     * @param Long $long Long to multiply with $this->
     *
     * @return Long the product of this and the $long->
     */
    public function multiply(Long $long)
    {
        if ($this->isZero() || $long->isZero()) {
            return static::ZERO();
        }

        if ($this->equals(static::MIN_VALUE())) {
            return $long->isOdd() ? static::MIN_VALUE() : static::ZERO();
        } elseif ($long->equals(static::MIN_VALUE())) {
            return $this->isOdd() ? static::MIN_VALUE() : static::ZERO();
        }

        if ($this->isNegative()) {
            if ($long->isNegative()) {
                return $this->negate()->multiply($long->negate());
            } else {
                return $this->negate()->multiply($long)->negate();
            }
        } elseif ($long->isNegative()) {
            return $this->multiply($long->negate())->negate();
        }

        // If both longs are small, use float multiplication
        if ($this->lessThan(static::TWO_PWR_24()) && $long->lessThan(static::TWO_PWR_24())) {
            return static::fromInt64($this->toInt64() * $long->toInt64());
        }

        $a48 = $this->zeroFill($this->high, 16);
        $a32 = $this->high & 0xFFFF;
        $a16 = $this->zeroFill($this->low, 16);
        $a00 = $this->low & 0xFFFF;

        $b48 = $this->zeroFill($long->high, 16);
        $b32 = $long->high & 0xFFFF;
        $b16 = $this->zeroFill($long->low, 16);
        $b00 = $long->low & 0xFFFF;

        $c48 = 0;
        $c32 = 0;
        $c16 = 0;
        $c00 = 0;

        $c00 += $a00 + $b00;
        $c16 += $this->zeroFill($c00, 16);
        $c00 &= 0xFFFF;
        $c16 += $a16 + $b16;
        $c32 += $this->zeroFill($c16, 16);
        $c16 &= 0xFFFF;
        $c32 += $a32 + $b32;
        $c48 += $this->zeroFill($c32, 16);
        $c32 &= 0xFFFF;
        $c48 += $a48 * $b00 + $a32 * $b16 + $a16 * $b32 + $a00 * $b48;
        $c48 &= 0xFFFF;

        return static::fromBits(($c16 << 16) | $c00, ($c48 << 16) | $c32);
    }

    /**
     * Returns this Long divided by the given one.
     *
     * @param Long $long Long by which to divide.
     *
     * @return Long this Long divided by the given one.
     * @throws \Exception
     */
    public function divide(Long $long)
    {
        if ($long->isZero()) {
            throw new \Exception('division by 0');
        } elseif ($this->isZero()) {
            return static::ZERO();
        }

        if ($this->equals(static::MIN_VALUE())) {
            if ($long->equals(static::ONE()) || $long->equals(static::NEG_ONE())) {
                return static::MIN_VALUE();
            } elseif ($long->equals(static::MIN_VALUE())) {
                return static::ONE();
            } else {
                // At this point, we have |other| >= 2, so |this/other| < |MIN_VALUE|.
                $halfThis = $this->shiftRight(1);
                $approx   = $halfThis->divide($long)->shiftLeft(1);
                if ($approx->equals(static::ZERO())) {
                    return $long->isNegative() ? static::ONE() : static::NEG_ONE();
                } else {
                    $rem    = $this->subtract($long->multiply($approx));
                    $result = $approx->add($rem->divide($long));

                    return $result;
                }
            }
        } else {
            if ($long->equals(static::MIN_VALUE())) {
                return static::ZERO();
            }
        }

        if ($this->isNegative()) {
            if ($long->isNegative()) {
                return $this->negate()->divide($long->negate());
            } else {
                return $this->negate()->divide($long)->negate();
            }
        } else {
            if ($long->isNegative()) {
                return $this->divide($long->negate())->negate();
            }
        }

        // Repeat the following until the remainder is less than other:  find a
        // floating-point that approximates remainder / other *from below*, add this
        // into the result, and subtract it from the remainder.  It is critical that
        // the approximate value is less than or equal to the real value so that the
        // remainder never becomes negative.
        $res = static::ZERO();
        $rem = $this;
        while ($rem->greaterThanOrEqual($long)) {
            // Approximate the result of division. This may be a little greater or
            // smaller than the actual value.
            $approx = max(1, floor($rem->toInt64() / $long->toInt64()));

            // We will tweak the approximate result by changing it in the 48-th digit or
            // the smallest non-fractional digit, whichever is larger.
            $log2  = ceil(log($approx) / log(2));
            $delta = ($log2 <= 48) ? 1 : pow(2, $log2 - 48);

            // Decrease the approximation until it is smaller than the remainder.  Note
            // that if it is too large, the product overflows and is negative.
            $approxRes = static::fromInt64($approx);
            $approxRem = $approxRes->multiply($long);
            while ($approxRem->isNegative() || $approxRem->greaterThan($rem)) {
                $approx    -= $delta;
                $approxRes = static::fromInt64($approx);
                $approxRem = $approxRes->multiply($long);
            }

            // We know the answer can't be zero... and actually, zero would cause
            // infinite recursion since we would make no progress.
            if ($approxRes->isZero()) {
                $approxRes = static::ONE();
            }

            $res = $res->add($approxRes);
            $rem = $rem->subtract($approxRem);
        }

        return $res;
    }

    /**
     * Returns this Long modulo the given one.
     *
     * @param Long $long Long by which to mod.
     *
     * @return Long this Long modulo the given one.
     */
    public function modulo(Long $long)
    {
        return $this->subtract($this->divide($long)->multiply($long));
    }

    /**
     * The bitwise-NOT of this value.
     *
     * @return Long the bitwise-NOT of this value.
     */
    public function not()
    {
        return static::fromBits(~$this->low, ~$this->high);
    }

    /**
     * Returns the bitwise-AND of this Long and the given one.
     *
     * @param Long $long the Long with which to AND.
     *
     * @return Long the bitwise-AND of this and the $long->
     */
    public function band(Long $long)
    {
        return static::fromBits($this->low & $long->low, $this->high & $long->high);
    }

    /**
     * Returns the bitwise-OR of this Long and the given one.
     *
     * @param Long $long the Long with which to OR.
     *
     * @return Long the bitwise-OR of this and the $long->
     */
    public function bor(Long $long)
    {
        return static::fromBits($this->low | $long->low, $this->high | $long->high);
    }

    /**
     * Returns the bitwise-XOR of this Long and the given one.
     *
     * @param Long $long the Long with which to XOR.
     *
     * @return Long the bitwise-XOR of this and the $long->
     */
    public function bxor(Long $long)
    {
        return static::fromBits($this->low ^ $long->low, $this->high ^ $long->high);
    }

    /**
     * Returns this Long with bits shifted to the left by the given amount.
     *
     * @param int $numBits the number of bits by which to shift.
     *
     * @return Long this shifted to the left by the given amount.
     */
    public function shiftLeft($numBits)
    {
        $numBits &= 63;
        if ($numBits == 0) {
            return $this;
        } else {
            $low = $this->low;
            if ($numBits < 32) {
                $high = $this->high;

                return static::fromBits($low << $numBits, $high << $numBits | $this->zeroFill($low, 32 - $numBits));
            } else {
                return static::fromBits(0, $low << ($numBits - 32));
            }
        }
    }

    /**
     * Returns this Long with bits shifted to the right by the given amount.
     *
     * @param int $numBits the number of bits by which to shift.
     *
     * @return Long this shifted to the right by the given amount.
     */
    public function shiftRight($numBits)
    {
        $numBits &= 63;
        if ($numBits == 0) {
            return $this;
        } else {
            $high = $this->high;
            if ($numBits < 32) {
                $low = $this->low;

                return static::fromBits(
                    $this->zeroFill($low, $numBits) | ($high << (32 - $numBits)),
                    $high >> $numBits
                );
            } else {
                return static::fromBits($high >> ($numBits - 32), $high >= 0 ? 0 : -1);
            }
        }
    }

    /**
     * Returns this Long with bits shifted to the right by the given amount, with the new top bits matching the current
     * sign bit.
     *
     * @param int $numBits the number of bits by which to shift.
     *
     * @return Long this shifted to the right by the given amount, with zeros placed into the new leading bits.
     */
    public function shiftRightUnsigned($numBits)
    {
        $numBits &= 63;
        if ($numBits == 0) {
            return $this;
        } else {
            $high = $this->high;
            if ($numBits < 32) {
                $low = $this->low;

                return static::fromBits(
                    $this->zeroFill($low, $numBits) | ($high << (32 - $numBits)),
                    $this->zeroFill($high, $numBits)
                );
            } else {
                if ($numBits == 32) {
                    return static::fromBits($high, 0);
                } else {
                    return static::fromBits($this->zeroFill($high, $numBits - 32), 0);
                }
            }
        }
    }

    private function zeroFill($a, $b)
    {
        if ($a >= 0) {
            return bindec(decbin($a >> $b)); //simply right shift for positive number
        }

        $bin = decbin($a >> $b);

        $bin = substr($bin, $b); // zero fill on the left side

        $o = bindec($bin);

        return $o;
    }
}