js/src/util/int.ts

// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.

/** @ignore */
const carryBit16 = 1 << 16;

/** @ignore */
function intAsHex(value: number): string {
    if (value < 0) {
        value = 0xFFFFFFFF + value + 1;
    }
    return `0x${value.toString(16)}`;
}

/** @ignore */
const kInt32DecimalDigits = 8;
/** @ignore */
const kPowersOfTen = [1,
                      10,
                      100,
                      1000,
                      10000,
                      100000,
                      1000000,
                      10000000,
                      100000000];

/** @ignore */
export class BaseInt64 {
    constructor (protected buffer: Uint32Array) {}

    public high(): number { return this.buffer[1]; }
    public low (): number { return this.buffer[0]; }

    protected _times(other: BaseInt64) {
        // Break the left and right numbers into 16 bit chunks
        // so that we can multiply them without overflow.
        const L = new Uint32Array([
            this.buffer[1] >>> 16,
            this.buffer[1] & 0xFFFF,
            this.buffer[0] >>> 16,
            this.buffer[0] & 0xFFFF
        ]);

        const R = new Uint32Array([
            other.buffer[1] >>> 16,
            other.buffer[1] & 0xFFFF,
            other.buffer[0] >>> 16,
            other.buffer[0] & 0xFFFF
        ]);

        let product = L[3] * R[3];
        this.buffer[0] = product & 0xFFFF;

        let sum = product >>> 16;

        product = L[2] * R[3];
        sum += product;

        product = (L[3] * R[2]) >>> 0;
        sum += product;

        this.buffer[0] += sum << 16;

        this.buffer[1] = (sum >>> 0 < product ? carryBit16 : 0);

        this.buffer[1] += sum >>> 16;
        this.buffer[1] += L[1] * R[3] + L[2] * R[2] + L[3] * R[1];
        this.buffer[1] += (L[0] * R[3] + L[1] * R[2] + L[2] * R[1] + L[3] * R[0]) << 16;

        return this;
      }

    protected _plus(other: BaseInt64) {
        const sum = (this.buffer[0] + other.buffer[0]) >>> 0;
        this.buffer[1] += other.buffer[1];
        if (sum < (this.buffer[0] >>> 0)) {
          ++this.buffer[1];
        }
        this.buffer[0] = sum;
    }

    public lessThan(other: BaseInt64): boolean {
        return this.buffer[1] < other.buffer[1] ||
            (this.buffer[1] === other.buffer[1] && this.buffer[0] < other.buffer[0]);
    }

    public equals(other: BaseInt64): boolean {
        return this.buffer[1] === other.buffer[1] && this.buffer[0] == other.buffer[0];
    }

    public greaterThan(other: BaseInt64): boolean {
        return other.lessThan(this);
    }

    public hex(): string {
        return `${intAsHex(this.buffer[1])} ${intAsHex(this.buffer[0])}`;
    }
}

/** @ignore */
export class Uint64 extends BaseInt64 {
    public times(other: Uint64): Uint64 {
        this._times(other);
        return this;
    }

    public plus(other: Uint64): Uint64 {
        this._plus(other);
        return this;
    }

    /** @nocollapse */
    public static from(val: any, out_buffer = new Uint32Array(2)): Uint64 {
        return Uint64.fromString(
            typeof(val) === 'string' ? val : val.toString(),
            out_buffer
        );
    }

    /** @nocollapse */
    public static fromNumber(num: number, out_buffer = new Uint32Array(2)): Uint64 {
        // Always parse numbers as strings - pulling out high and low bits
        // directly seems to lose precision sometimes
        // For example:
        //     > -4613034156400212000 >>> 0
        //     721782784
        // The correct lower 32-bits are 721782752
        return Uint64.fromString(num.toString(), out_buffer);
    }

    /** @nocollapse */
    public static fromString(str: string, out_buffer = new Uint32Array(2)): Uint64 {
        const length = str.length;

        const out = new Uint64(out_buffer);
        for (let posn = 0; posn < length;) {
            const group = kInt32DecimalDigits < length - posn ?
                          kInt32DecimalDigits : length - posn;
            const chunk = new Uint64(new Uint32Array([parseInt(str.substr(posn, group), 10), 0]));
            const multiple = new Uint64(new Uint32Array([kPowersOfTen[group], 0]));

            out.times(multiple);
            out.plus(chunk);

            posn += group;
        }

        return out;
    }

    /** @nocollapse */
    public static convertArray(values: (string|number)[]): Uint32Array {
        const data = new Uint32Array(values.length * 2);
        for (let i = -1, n = values.length; ++i < n;) {
            Uint64.from(values[i], new Uint32Array(data.buffer, data.byteOffset + 2 * i * 4, 2));
        }
        return data;
    }

    /** @nocollapse */
    public static multiply(left: Uint64, right: Uint64): Uint64 {
        const rtrn = new Uint64(new Uint32Array(left.buffer));
        return rtrn.times(right);
    }

    /** @nocollapse */
    public static add(left: Uint64, right: Uint64): Uint64 {
        const rtrn = new Uint64(new Uint32Array(left.buffer));
        return rtrn.plus(right);
    }
}

/** @ignore */
export class Int64 extends BaseInt64 {
    public negate(): Int64 {
        this.buffer[0] = ~this.buffer[0] + 1;
        this.buffer[1] = ~this.buffer[1];

        if (this.buffer[0] == 0) { ++this.buffer[1]; }
        return this;
    }

    public times(other: Int64): Int64 {
        this._times(other);
        return this;
    }

    public plus(other: Int64): Int64 {
        this._plus(other);
        return this;
    }

    public lessThan(other: Int64): boolean {
        // force high bytes to be signed
        const this_high = this.buffer[1] << 0;
        const other_high = other.buffer[1] << 0;
        return this_high < other_high ||
            (this_high === other_high && this.buffer[0] < other.buffer[0]);
    }

    /** @nocollapse */
    public static from(val: any, out_buffer = new Uint32Array(2)): Int64 {
        return Int64.fromString(
            typeof(val) === 'string' ? val : val.toString(),
            out_buffer
        );
    }

    /** @nocollapse */
    public static fromNumber(num: number, out_buffer = new Uint32Array(2)): Int64 {
        // Always parse numbers as strings - pulling out high and low bits
        // directly seems to lose precision sometimes
        // For example:
        //     > -4613034156400212000 >>> 0
        //     721782784
        // The correct lower 32-bits are 721782752
        return Int64.fromString(num.toString(), out_buffer);
    }

    /** @nocollapse */
    public static fromString(str: string, out_buffer = new Uint32Array(2)): Int64 {
        // TODO: Assert that out_buffer is 0 and length = 2
        const negate = str.startsWith('-');
        const length = str.length;

        const out = new Int64(out_buffer);
        for (let posn = negate ? 1 : 0; posn < length;) {
            const group = kInt32DecimalDigits < length - posn ?
                          kInt32DecimalDigits : length - posn;
            const chunk = new Int64(new Uint32Array([parseInt(str.substr(posn, group), 10), 0]));
            const multiple = new Int64(new Uint32Array([kPowersOfTen[group], 0]));

            out.times(multiple);
            out.plus(chunk);

            posn += group;
        }
        return negate ? out.negate() : out;
    }

    /** @nocollapse */
    public static convertArray(values: (string|number)[]): Uint32Array {
        const data = new Uint32Array(values.length * 2);
        for (let i = -1, n = values.length; ++i < n;) {
            Int64.from(values[i], new Uint32Array(data.buffer, data.byteOffset + 2 * i * 4, 2));
        }
        return data;
    }

    /** @nocollapse */
    public static multiply(left: Int64, right: Int64): Int64 {
        const rtrn = new Int64(new Uint32Array(left.buffer));
        return rtrn.times(right);
    }

    /** @nocollapse */
    public static add(left: Int64, right: Int64): Int64 {
        const rtrn = new Int64(new Uint32Array(left.buffer));
        return rtrn.plus(right);
    }
}

/** @ignore */
export class Int128 {
    constructor (private buffer: Uint32Array) {
        // buffer[3] MSB (high)
        // buffer[2]
        // buffer[1]
        // buffer[0] LSB (low)
    }

    public high(): Int64 {
        return new Int64(new Uint32Array(this.buffer.buffer, this.buffer.byteOffset + 8, 2));
    }

    public low(): Int64 {
        return new Int64(new Uint32Array(this.buffer.buffer, this.buffer.byteOffset, 2));
    }

    public negate(): Int128 {
        this.buffer[0] = ~this.buffer[0] + 1;
        this.buffer[1] = ~this.buffer[1];
        this.buffer[2] = ~this.buffer[2];
        this.buffer[3] = ~this.buffer[3];

        if (this.buffer[0] == 0) { ++this.buffer[1]; }
        if (this.buffer[1] == 0) { ++this.buffer[2]; }
        if (this.buffer[2] == 0) { ++this.buffer[3]; }
        return this;
    }

    public times(other: Int128): Int128 {
        // Break the left and right numbers into 32 bit chunks
        // so that we can multiply them without overflow.
        const L0 = new Uint64(new Uint32Array([this.buffer[3],  0]));
        const L1 = new Uint64(new Uint32Array([this.buffer[2],  0]));
        const L2 = new Uint64(new Uint32Array([this.buffer[1],  0]));
        const L3 = new Uint64(new Uint32Array([this.buffer[0],  0]));

        const R0 = new Uint64(new Uint32Array([other.buffer[3], 0]));
        const R1 = new Uint64(new Uint32Array([other.buffer[2], 0]));
        const R2 = new Uint64(new Uint32Array([other.buffer[1], 0]));
        const R3 = new Uint64(new Uint32Array([other.buffer[0], 0]));

        let product = Uint64.multiply(L3, R3);
        this.buffer[0] = product.low();

        const sum = new Uint64(new Uint32Array([product.high(), 0]));

        product = Uint64.multiply(L2, R3);
        sum.plus(product);

        product = Uint64.multiply(L3, R2);
        sum.plus(product);

        this.buffer[1] = sum.low();

        this.buffer[3] = (sum.lessThan(product) ? 1 : 0);

        this.buffer[2] = sum.high();
        const high = new Uint64(new Uint32Array(this.buffer.buffer, this.buffer.byteOffset + 8, 2));

        high.plus(Uint64.multiply(L1, R3))
            .plus(Uint64.multiply(L2, R2))
            .plus(Uint64.multiply(L3, R1));
        this.buffer[3] += Uint64.multiply(L0, R3)
                        .plus(Uint64.multiply(L1, R2))
                        .plus(Uint64.multiply(L2, R1))
                        .plus(Uint64.multiply(L3, R0)).low();

        return this;
    }

    public plus(other: Int128): Int128 {
        const sums = new Uint32Array(4);
        sums[3] = (this.buffer[3] + other.buffer[3]) >>> 0;
        sums[2] = (this.buffer[2] + other.buffer[2]) >>> 0;
        sums[1] = (this.buffer[1] + other.buffer[1]) >>> 0;
        sums[0] = (this.buffer[0] + other.buffer[0]) >>> 0;

        if (sums[0] < (this.buffer[0] >>> 0)) {
            ++sums[1];
        }
        if (sums[1] < (this.buffer[1] >>> 0)) {
            ++sums[2];
        }
        if (sums[2] < (this.buffer[2] >>> 0)) {
            ++sums[3];
        }

        this.buffer[3] = sums[3];
        this.buffer[2] = sums[2];
        this.buffer[1] = sums[1];
        this.buffer[0] = sums[0];

        return this;
    }

    public hex(): string {
        return `${intAsHex(this.buffer[3])} ${intAsHex(this.buffer[2])} ${intAsHex(this.buffer[1])} ${intAsHex(this.buffer[0])}`;
    }

    /** @nocollapse */
    public static multiply(left: Int128, right: Int128): Int128 {
        const rtrn = new Int128(new Uint32Array(left.buffer));
        return rtrn.times(right);
    }

    /** @nocollapse */
    public static add(left: Int128, right: Int128): Int128 {
        const rtrn = new Int128(new Uint32Array(left.buffer));
        return rtrn.plus(right);
    }

    /** @nocollapse */
    public static from(val: any, out_buffer = new Uint32Array(4)): Int128 {
        return Int128.fromString(
            typeof(val) === 'string' ? val : val.toString(),
            out_buffer
        );
    }

    /** @nocollapse */
    public static fromNumber(num: number, out_buffer = new Uint32Array(4)): Int128 {
        // Always parse numbers as strings - pulling out high and low bits
        // directly seems to lose precision sometimes
        // For example:
        //     > -4613034156400212000 >>> 0
        //     721782784
        // The correct lower 32-bits are 721782752
        return Int128.fromString(num.toString(), out_buffer);
    }

    /** @nocollapse */
    public static fromString(str: string, out_buffer = new Uint32Array(4)): Int128 {
        // TODO: Assert that out_buffer is 0 and length = 4
        const negate = str.startsWith('-');
        const length = str.length;

        const out = new Int128(out_buffer);
        for (let posn = negate ? 1 : 0; posn < length;) {
            const group = kInt32DecimalDigits < length - posn ?
                          kInt32DecimalDigits : length - posn;
            const chunk = new Int128(new Uint32Array([parseInt(str.substr(posn, group), 10), 0, 0, 0]));
            const multiple = new Int128(new Uint32Array([kPowersOfTen[group], 0, 0, 0]));

            out.times(multiple);
            out.plus(chunk);

            posn += group;
        }

        return negate ? out.negate() : out;
    }

    /** @nocollapse */
    public static convertArray(values: (string|number)[]): Uint32Array {
        // TODO: Distinguish between string and number at compile-time
        const data = new Uint32Array(values.length * 4);
        for (let i = -1, n = values.length; ++i < n;) {
            Int128.from(values[i], new Uint32Array(data.buffer, data.byteOffset + 4 * 4 * i, 4));
        }
        return data;
    }
}