UInt96.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 96-bit unsigned integer.
 *
 * <p>This is a specialised class to implement an accumulator of {@code long} values
 * generated by squaring {@code int} values from an array (max observations=2^31).
 *
 * @since 1.1
 */
final class UInt96 {
    /** Mask for the lower 32-bits of a long. */
    private static final long MASK32 = 0xffff_ffffL;

    // Low data is stored using an integer to allow efficient sum-with-carry addition

    /** bits 32-1 (low 32-bits). */
    private int c;
    /** bits 96-33. */
    private long ab;

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

    /**
     * Create an instance.
     *
     * @param x Value.
     */
    private UInt96(long x) {
        c = (int) x;
        ab = (int) (x >>> Integer.SIZE);
    }

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

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

    /**
     * Create an instance of the {@code long} value.
     * The value is assumed to be an unsigned 64-bit integer.
     *
     * @param x Value (must be positive).
     * @return the instance
     */
    static UInt96 of(long x) {
        return new UInt96(x);
    }

    /**
     * Adds the value. 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.
        final long s = x + (c & MASK32);
        c = (int) s;
        ab += s >>> Integer.SIZE;
    }

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

    /**
     * Convert to a BigInteger.
     *
     * @return the value
     */
    BigInteger toBigInteger() {
        if (ab != 0) {
            final ByteBuffer bb = ByteBuffer.allocate(Integer.BYTES * 3)
                .putLong(ab)
                .putInt(c);
            return new BigInteger(1, bb.array());
        }
        return BigInteger.valueOf(c & MASK32);
    }

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

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