long.ts

const DIGITS = [
  '0', '1', '2', '3', '4', '5', '6', '7',
  '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'
];
const TWO_TO_32 = 0x100000000;
const MAX_SAFE_INTEGER = 0x1FFFFFFFFFFFFF;

export class UInt64 {

  readonly low: number;
  readonly high: number;

  constructor(low: number, high: number) {
    this.low = low;
    this.high = high;
  }

  static fromNumber(value: number): UInt64 {
    const low = value >>> 0;
    const high = Math.floor((value - low) / TWO_TO_32) >>> 0;
    return UInt64.fromBits(low, high);
  }

  static fromString(s: string): UInt64 {
    // We can avoid very expensive multiply based code path for some common cases.
    const numberValue = +s;
    if (numberValue <= MAX_SAFE_INTEGER) {
      return UInt64.fromNumber(numberValue);
    }

    // Do several (8) digits each time through the loop, so as to
    // minimize the calls to the very expensive emulated multiply.
    var result = UInt64.fromBits(0, 0);
    for (let i = 0; i < s.length; i += 8) {
      const size = Math.min(8, s.length - i);
      const value = +s.substring(i, i + size);
      if (size < 8) {
        const power = UInt64.fromBits(Math.pow(10, size), 0);
        result = result.multiply(power).add(UInt64.fromBits(value, 0));
      } else {
        result = result.multiply(UInt64.fromBits(100000000, 0)).add(UInt64.fromBits(value, 0));
      }
    }

    return result;
  }

  static fromBits(low: number, high: number): UInt64 {
    return new UInt64(low, high);
  }

  unsafeToNumber(): number {
    return this.high * TWO_TO_32 + this.low;
  }

  add(other: UInt64): UInt64 {
    const low = ((this.low + other.low) & 0xFFFFFFFF) >>> 0;
    const high =
      (((this.high + other.high) & 0xFFFFFFFF) >>> 0) +
      (((this.low + other.low) >= 0x100000000) ? 1 : 0);
    return new UInt64(low >>> 0, high >>> 0);
  }

  multiply(other: UInt64): UInt64 {
    // Divide each long into 4 chunks of 16 bits, and then add up 4x4 products.
    // We can skip products that would overflow.
    const a48 = this.high >>> 16;
    const a32 = this.high & 0xFFFF;
    const a16 = this.low >>> 16;
    const a00 = this.low & 0xFFFF;

    const b48 = other.high >>> 16;
    const b32 = other.high & 0xFFFF;
    const b16 = other.low >>> 16;
    const b00 = other.low & 0xFFFF;

    let c48 = 0, c32 = 0, c16 = 0, c00 = 0;
    c00 += a00 * b00;
    c16 += c00 >>> 16;
    c00 &= 0xFFFF;
    c16 += a16 * b00;
    c32 += c16 >>> 16;
    c16 &= 0xFFFF;
    c16 += a00 * b16;
    c32 += c16 >>> 16;
    c16 &= 0xFFFF;
    c32 += a32 * b00;
    c48 += c32 >>> 16;
    c32 &= 0xFFFF;
    c32 += a16 * b16;
    c48 += c32 >>> 16;
    c32 &= 0xFFFF;
    c32 += a00 * b32;
    c48 += c32 >>> 16;
    c32 &= 0xFFFF;
    c48 += a48 * b00 + a32 * b16 + a16 * b32 + a00 * b48;
    c48 &= 0xFFFF;

    return new UInt64((c16 << 16) | c00, (c48 << 16) | c32);
  }

  subtract(other: UInt64): UInt64 {
    const low = ((this.low - other.low) & 0xffffffff) >>> 0;
    const high =
      (((this.high - other.high) & 0xffffffff) >>> 0) -
      (((this.low - other.low) < 0) ? 1 : 0);
    return new UInt64(low >>> 0, high >>> 0);
  };

  toString(): string {
    // Skip the expensive conversion if the number is small enough to use the
    // built-in conversions.
    if (this.high <= 0x1FFFFF) {
      return '' + this.unsafeToNumber();
    }

    // What this code is doing is essentially converting the input number from
    // base-2 to base-1e7, which allows us to represent the 64-bit range with
    // only 3 (very large) digits. Those digits are then trivial to convert to
    // a base-10 string.

    // The magic numbers used here are -
    // 2^24 = 16777216 = (1,6777216) in base-1e7.
    // 2^48 = 281474976710656 = (2,8147497,6710656) in base-1e7.

    // Split 32:32 representation into 16:24:24 representation so our
    // intermediate digits don't overflow.
    const low = this.low & 0xFFFFFF;
    const mid = (((this.low >>> 24) | (this.high << 8)) >>> 0) & 0xFFFFFF;
    const high = (this.high >> 16) & 0xFFFF;

    // Assemble our three base-1e7 digits, ignoring carries. The maximum
    // value in a digit at this step is representable as a 48-bit integer, which
    // can be stored in a 64-bit floating point number.
    let digitA = low + (mid * 6777216) + (high * 6710656);
    let digitB = mid + (high * 8147497);
    let digitC = (high * 2);

    // Apply carries from A to B and from B to C.
    const base = 10000000;
    if (digitA >= base) {
      digitB += Math.floor(digitA / base);
      digitA %= base;
    }

    if (digitB >= base) {
      digitC += Math.floor(digitB / base);
      digitB %= base;
    }

    // Convert base-1e7 digits to base-10, omitting leading zeroes.
    let start = false;
    let result = '';

    function emit(digit: number) {
      let temp = base;
      for (let i = 0; i < 7; i++) {
        temp /= 10;
        let decimalDigit = ((digit / temp) % 10) >>> 0;
        if ((decimalDigit == 0) && !start) continue;
        start = true;
        result += DIGITS[decimalDigit];
      }
    }

    if (digitC || start) emit(digitC);
    if (digitB || start) emit(digitB);
    if (digitA || start) emit(digitA);

    return result;
  }
}

export class Int64 {

  readonly low: number;
  readonly high: number;

  constructor(low: number, high: number) {
    this.low = low;
    this.high = high;
  }

  static fromString(s: string): Int64 {
    const hasNegative = (s.length > 0 && s[0] == '-');
    const numberString = hasNegative ? s.substring(1) : s;
    const unsigned = UInt64.fromString(numberString);
    const signed = hasNegative ? UInt64.fromBits(0, 0).subtract(unsigned) : unsigned;
    return new Int64(signed.low, signed.high);
  }

  toString(): string {
    const negative = (this.high & 0x80000000);
    const low = negative ? (~this.low + 1) >>> 0 : this.low;
    const high = negative ? (~this.high + ((this.low == 0) ? 1 : 0)) >>> 0 : this.high;
    const signed = UInt64.fromBits(low, high);
    return (negative ? '-' : '') + signed.toString();
  }
}