UInt128.java

/*
 * 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.
 */
package org.apache.commons.statistics.descriptive;

import java.math.BigInteger;
import java.nio.ByteBuffer;

/**
 * A mutable 128-bit unsigned integer.
 *
 * <p>This is a specialised class to implement an accumulator of {@code long} values
 * generated by squaring {@code int} values.
 *
 * @since 1.1
 */
final class UInt128 {
    /** Mask for the lower 32-bits of a long. */
    private static final long MASK32 = 0xffff_ffffL;

    // Data is stored using integers to allow efficient sum-with-carry addition

    /** bits 32-1 (low 32-bits). */
    private int d;
    /** bits 64-33. */
    private int c;
    /** bits 128-65. */
    private long ab;

    /**
     * Create an instance.
     */
    private UInt128() {
        // No-op
    }

    /**
     * Create an instance using a direct binary representation.
     *
     * @param hi High 64-bits.
     * @param mid Middle 32-bits.
     * @param lo Low 32-bits.
     */
    private UInt128(long hi, int mid, int lo) {
        this.d = lo;
        this.c = mid;
        this.ab = hi;
    }

    /**
     * Create an instance using a direct binary representation.
     * This is package-private for testing.
     *
     * @param hi High 64-bits.
     * @param lo Low 64-bits.
     */
    UInt128(long hi, long lo) {
        this.d = (int) lo;
        this.c = (int) (lo >>> Integer.SIZE);
        this.ab = hi;
    }

    /**
     * Create an instance. The initial value is zero.
     *
     * @return the instance
     */
    static UInt128 create() {
        return new UInt128();
    }

    /**
     * Create an instance of the {@code UInt96} value.
     *
     * @param x Value.
     * @return the instance
     */
    static UInt128 of(UInt96 x) {
        final int lo = x.lo32();
        final long hi = x.hi64();
        final UInt128 y = new UInt128();
        y.d = lo;
        y.c = (int) hi;
        y.ab = hi >>> Integer.SIZE;
        return y;
    }

    /**
     * Adds the value in place. It is assumed to be positive, for example the square of an
     * {@code int} value. However no check is performed for a negative value.
     *
     * <p>Note: This addition handles {@value Long#MIN_VALUE} as an unsigned
     * value of 2^63.
     *
     * @param x Value.
     */
    void addPositive(long x) {
        // Sum with carry.
        // Assuming x is positive then x + lo will not overflow 64-bits
        // so we do not have to split x into upper and lower 32-bit values.
        long s = x + (d & MASK32);
        d = (int) s;
        s = (s >>> Integer.SIZE) + (c & MASK32);
        c = (int) s;
        ab += s >>> Integer.SIZE;
    }

    /**
     * Adds the value in-place.
     *
     * @param x Value.
     */
    void add(UInt128 x) {
        // Avoid issues adding to itself
        final int dd = x.d;
        final int cc = x.c;
        final long aabb = x.ab;
        // Sum with carry.
        long s = (dd & MASK32) + (d & MASK32);
        d = (int) s;
        s = (s >>> Integer.SIZE) + (cc & MASK32) + (c & MASK32);
        c = (int) s;
        ab += (s >>> Integer.SIZE) + aabb;
    }

    /**
     * Multiply by the unsigned value.
     * Any overflow bits are lost.
     *
     * @param x Value.
     * @return the product
     */
    UInt128 unsignedMultiply(int x) {
        final long xx = x & MASK32;
        // Multiply with carry.
        long product = xx * (d & MASK32);
        final int dd = (int) product;
        product = (product >>> Integer.SIZE) + xx * (c & MASK32);
        final int cc = (int) product;
        // Possible overflow here and bits are lost
        final long aabb = (product >>> Integer.SIZE) + xx * ab;
        return new UInt128(aabb, cc, dd);
    }

    /**
     * Subtracts the value.
     * Any overflow bits (negative result) are lost.
     *
     * @param x Value.
     * @return the difference
     */
    UInt128 subtract(UInt128 x) {
        // Difference with carry.
        long diff = (d & MASK32) - (x.d & MASK32);
        final int dd = (int) diff;
        diff = (diff >> Integer.SIZE) + (c & MASK32) - (x.c & MASK32);
        final int cc = (int) diff;
        // Possible overflow here and bits are lost containing info on the
        // magnitude of the true negative value
        final long aabb = (diff >> Integer.SIZE) + ab - x.ab;
        return new UInt128(aabb, cc, dd);
    }

    /**
     * Convert to a BigInteger.
     *
     * @return the value
     */
    BigInteger toBigInteger() {
        // Test if we have more than 63-bits
        if (ab != 0 || c < 0) {
            return new BigInteger(1, ByteBuffer.allocate(Integer.BYTES * 4)
                .putLong(ab)
                .putInt(c)
                .putInt(d).array());
        }
        // Create from a long
        return BigInteger.valueOf(lo64());
    }

    /**
     * Convert to a {@code double}.
     *
     * @return the value
     */
    double toDouble() {
        return IntMath.uint128ToDouble(hi64(), lo64());
    }

    /**
     * Convert to an {@code int}; throwing an exception if the value overflows an {@code int}.
     *
     * @return the value
     * @throws ArithmeticException if the value overflows an {@code int}.
     * @see Math#toIntExact(long)
     */
    int toIntExact() {
        return Math.toIntExact(toLongExact());
    }

    /**
     * Convert to a {@code long}; throwing an exception if the value overflows a {@code long}.
     *
     * @return the value
     * @throws ArithmeticException if the value overflows a {@code long}.
     */
    long toLongExact() {
        // Test if we have more than 63-bits
        if (ab != 0 || c < 0) {
            throw new ArithmeticException("long integer overflow");
        }
        return lo64();
    }

    /**
     * Return the lower 64-bits as a {@code long} value.
     *
     * @return bits 64-1
     */
    long lo64() {
        return (d & MASK32) | ((c & MASK32) << Integer.SIZE);
    }

    /**
     * Return the low 32-bits as an {@code int} value.
     *
     * @return bits 32-1
     */
    int lo32() {
        return d;
    }

    /**
     * Return the middle 32-bits as an {@code int} value.
     *
     * @return bits 64-33
     */
    int mid32() {
        return c;
    }

    /**
     * Return the higher 64-bits as a {@code long} value.
     *
     * @return bits 128-65
     */
    long hi64() {
        return ab;
    }
}